Algorithm code problem

This is a discussion on Algorithm code problem within the C Programming forums, part of the General Programming Boards category; Ok i have the fallowing problem with this code. Exemple: If i have frame size 4, the first 4 numbers ...

  1. #1
    Registered User
    Join Date
    Jan 2012
    Posts
    6

    Algorithm code problem

    Ok i have the fallowing problem with this code. Exemple: If i have frame size 4, the first 4 numbers from string are stored correctly into the frame, but when the numbers in frame need to be replaced it replaces only the number which is in last spot of frame, so the algoritm isnt working correctly because of this.

    here i read the string from a file and store it into array
    Code:
     
                         .
                         . 
                         .
                         . 
                int num_frames= atoi(argv[1]);
                int frames[num_frames];
                int error=0;
                int j, avail,k;
                int n,b,v;
                int index_frame=-1;
                int idx_p=-1;
                int idx_pbest=-1;
                int idx_f=-1;
                
    
                for(i=0;i<num_frames;i++)
                {
                    frames[i]= -1;
                }
    
                
                for(i=0;i<count;i++)
                {
                    avail=0;
                   for(k=0;k<num_frames;k++)
                    {
                        if(frame[k]==ref_string[i])
                        {
                            printf("found %d: ",ref_string[i]);
                            for(k=0;k<num_frames;k++)
                         {                                      
                                printf(" %s %d","|",frame[k]);
                            }
                             avail=1;
                        }
                    }
            
                  if (avail==0)
                  {
                        for(k=0;k<num_frames; k++)
                        {
                            if(frames[k]==-1)
                            {
                                index_frame=k;
                                break;
                            }
                        }        
                        
                        for(b=0; b<num_frames;b++)    
                        {
                            for(v=count-1; v>= i ;v--)
                            {
                                if(frame[b]==ref_string[v])
                                {
                                    idx_p=v;
                                }
                            }
    
                            if(idx_pbest<idx_p)
                            {
                                idx_pbest=idx_p;
                                idx_f=b;
                            }        
                        }
    
                        if(index_frame !=-1)
                        {
                            
                            frame[index_frame]=ref_string[i];
    
                        }
                        else
                        {    
            
                                frames[idx_f]=ref_string[i];
                
                        }
    
                        
                        printf("insert %d: ",ref_string[i]);
                     error++;
                
                     for(k=0;k<num_frames;k++)
                     {                                      
                        printf(" %s %d","|",frames[k]);
                        }
                    }
                   printf("\n");
        
                }
               printf("Errors: %d%s",error,"\n");
    
            }
    
       return 0;
    The algorithm is opt algorithm for page replacement

    Ty for you help!


  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Write out in words what it is you are actually trying to do. Don't take short cuts like "move a frame", say what that means exactly. Then turn those words into pseudo code. For example:

    Words: "Swap two numbers."

    Store one of the two numbers in a temporary variable.
    Copy the second number over top of the first.
    Copy the temporary number over top of the second.

    Pseudo code:
    Code:
    temp = num1
    num1 = num2
    num2 = temp
    If you can't do something like that for what you are trying to do, then you don't understand your problem, and won't be able to actually program it.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Jan 2012
    Posts
    6
    Well do you know where the error is? I was looking at this code whole day and i didnt find why it is not working corectly....

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Keep looking, because until you can do what I said, you won't understand how to program it, and I am not going to do it for you.


    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    I cant work out what it's supposed to do from the description. Perhaps some examples of what it should do would help?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Jan 2012
    Posts
    6
    But i do know what it needs to do, just cant find the error. It supose to insert numbers from string to another array(reprisenting memory in computer, num of blocks). Than it checks if the number already exists in the array if it doesnt than it goes to look which number from frames array(blocks of memory) wont be used the longest(compers to string of numbers). That number should be than replaced with the number in ref string. But i dont know why it replace only the last number. Help!

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Why is it so hard for you to do what was asked of you?


    Quzah.
    Hope is the first step on the road to disappointment.

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Could you give a simple example of the input and output so that we can understand what it does please?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Jan 2012
    Posts
    6
    Ok. So input is ref string that is read from file : 6 7 5 1 4 0 5 6 3 2 1 4 7 0 2 4 3 1 5 0 and numbers of frames are 3.

    Output:

    insert 6: | 6 | -1 | -1
    insert 7: | 6 | 7 | -1
    insert 5: | 6 | 7 | 5
    insert 1: | 6 | 7 | 1
    insert 4: | 6 | 7 | 4
    insert 0: | 6 | 7 | 0
    insert 5: | 6 | 7 | 5
    found 6: | 6 | 7 | 5
    insert 3: | 6 | 7 | 3
    insert 2: | 6 | 7 | 2
    insert 1: | 6 | 7 | 1
    insert 4: | 6 | 7 | 4
    found 7: | 6 | 7 | 4
    insert 0: | 6 | 7 | 0
    insert 2: | 6 | 7 | 2
    insert 4: | 6 | 7 | 4
    insert 3: | 6 | 7 | 3
    insert 1: | 6 | 7 | 1
    insert 5: | 6 | 7 | 5
    insert 0: | 6 | 7 | 0
    Errors: 18

    You can se that the first 3 values are inserted correctly, but when there is no space in frames anymore it always replaces the last number. This algorithem should replace that number in frame which is not used for the longest time in the ref string.

    Help pls!

  10. #10
    Registered User
    Join Date
    May 2009
    Posts
    2,371
    If I understand you are saying "insert 1" line was done wrong.
    Code:
    insert 6: | 6 | -1 | -1
    insert 7: | 6 | 7 | -1
    insert 5: | 6 | 7 | 5
    insert 1: | 6 | 7 | 1
    What is the correct way

    Code:
    insert 1: | 7 | 5 | 1
    or

    Code:
    insert 1: | 1 | 7 | 5
    NOTE: You really NEED to write out the algorithm you are trying to follow it words as quzah asked!

    Tim S.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  11. #11
    Registered User
    Join Date
    Jan 2012
    Posts
    6
    First 3 lines are ok.
    Code:
    insert 6:  | 6 | -1 | -1
    insert 7:  | 6 | 7 | -1
    insert 5:  | 6 | 7 | 5
    Down from here there is all wrong. It always insert the numbers to the last spot of frames. But it should look which number in frames wont be used for the longest time(numbers are compared to reference string.

    Here is where it look which is number is used last.
    Code:
                          for(b=0;b<num_frames;b++)
                          {
                                for(v=count-1; v>=i; v--)
                                {
                                    if(frames[b]==ref_string[v])
                                    {
                                        idx_p=v;
                                    }
                                }
    
                                if(idx_pbest<idx_p)
                                {
                                    idx_pbest=idx_p;
                                    idx_f=b;
                                }
                          }
    The correct output would be like this( ref string: 6 7 5 1 4 0 5 6 3 2 1 4 7 0 2 4 3 1 5 0 num of frames:3)

    -1|-1|-1:
    6|-1|-1:
    6|7|-1:
    6|7|5:
    6|1|5:
    6|4|5:
    6|0|5:
    6|0|5:
    6|0|5:
    3|0|5:
    3|0|2:
    1|0|2:
    4|0|2:
    7|0|2:
    7|0|2:
    7|0|2:
    4|0|2:
    3|0|2:
    1|0|2:
    5|0|2:
    5|0|2

  12. #12
    Registered User
    Join Date
    Jan 2012
    Posts
    6
    Ok figure it out... Ty anyway!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 55
    Last Post: 12-14-2011, 02:58 AM
  2. Understanding Genetic Algorithm Code!!
    By L3munoz in forum C Programming
    Replies: 2
    Last Post: 10-25-2010, 06:53 AM
  3. what is the algorithm in this problem..
    By cfan in forum C Programming
    Replies: 2
    Last Post: 08-04-2009, 11:52 AM
  4. need source code for Cohen sutherland algorithm
    By specks5317 in forum C++ Programming
    Replies: 1
    Last Post: 10-17-2002, 08:24 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21