Board index » delphi » URGENT ** Problem with Iteration ** URGENT

URGENT ** Problem with Iteration ** URGENT

Hi, I am a student with an assignment program I cannot get to work
properly. The assignment deals primarely with recursion, and that I
get to work.

The program is to make a list of numbers, write them to screen, ask
the user for a number and check the list if the number is there. The
checking should work both with recursion and iteration. The recursion
works every time, but the iteration routine rapports that the number
does not exist if it exists. This happens at more or less regular
intervals.

Control with indata is not an issue in htis exersice.

If you have a compier, pls try it out and give me som hint as to the
error.

The program is originally written in Norwegian, but I hope the
translation is readable.
Try it out with different values for Max, just remember that it has to
be a multiple of 15!

With Max=30 the iteration makes an error on even places.
With Max=300 the mistakes comes more often.

Program Rekursjon;

Uses
   crt;

Const
   Max = 30;

Type
   Table = Array [1..Max] of Integer;

Var
   NumberList : Table;
   L, R, x, RNumber, INumber : Integer;

{*********************************************}

Procedure WriteTable(Var NumberList:Table);

Var   i, k, l, value : Integer;

Begin
   i := 1;
   l := 1;
   value := 1;

   Writeln;
   Write('  ');
   For k := 1 to 15 do
         Write(k:5);
   Writeln;
   Write('  ');
   For k := 1 to 75 do
         Write('-');
   Writeln;

   While i < Max do
      Begin {while}
         Write(l:2);
         Write('|');
         For k := 1 to 15 do
            Begin {for}
               value := value + (random(2) + 1);
               NumberList[i] := value;
               Write(NumberList[i]:5);
               i := i + 1;
            End;  {for}
         Writeln;
         l := l + 1;
      End;  {while}
End;

{*********************************************}

Procedure FindNumberR(NumberList:Table;L, R, x:Integer; Var
RNumber:Integer);

Var
   m : Integer;

Begin
   If L = R then
      Begin {if}
         m := R;
         If NumberList[m] = x then
            Writeln('The number ', x, ' exists')
         Else
            Writeln('The number ', x, ' does not exist');
      End   {if}
   Else
      Begin {else}
         RNumber := RNumber + 1;
         m := (L + R) div 2;
         If NumberList[m] < x then
            Begin
               L := m + 1;
               FindNumberR(NumberList, L, R, x, RNumber);
            End
         Else
            Begin
               R := m;
               FindNumberR(NumberList, L, R, x, RNumber);
            End;
   End;  {else}
End;

{*********************************************}

Procedure FindNumberI(NumberList:Table;L, R, x:Integer; Var
INumber:Integer);

Var
   m : Integer;

Begin
   INumber := 0;
   While (L < R) do
      Begin {while}
         INumber := INumber + 1;
         m := (L + R) div 2;
         If NumberList[m] < x then
            L := m + 1
         Else
            R := m;
      End;  {while}
      If NumberList[m] = x then
         Writeln('The number ', x, ' exists')
      Else
         Writeln('The number ', x, ' does not exist');
End;

{*********************************************}

Begin {Hovedalgoritme}
   Randomize;
   L := 0;
   R := Max;
   WriteTable(NumberList);
   Writeln;
   Write('Which Number do you want to find? ');
   Readln(x);
   Writeln;
   Writeln('Recursivt search:');
   FinnNumberR(NumberList, L, R, x, RNumber);
   Writeln('The recursion looped ', RNumber, ' times.');
   Writeln;
   Writeln('Iterativt search:');
   FinnNumberI(NumberList, L, R, x, INumber);
   Writeln('The iteration looped ', INumber, ' times.');
End.  {Hovedalgoritme}

{*********************************************}

If possible, pls send the reply by e-mail as well as posting it.
Fredrik

=======================================================
"640k should be enough for anybody" - Bill Gates, 1981.

Fredrik Endresen
Po.box 206             Voice: (+47) 75 05 68 17
N-8700 Nesna           e-mail:  f...@nord.eunet.no
Norway                 http://login.nord.eunet.no/~fe/
=======================================================

 

Re:URGENT ** Problem with Iteration ** URGENT


Quote
f...@nord.eunet.no (Fredrik Endresen) wrote:
>The program is to make a list of numbers, write them to screen, ask
>the user for a number and check the list if the number is there. The
>checking should work both with recursion and iteration. The recursion
>works every time, but the iteration routine rapports that the number
>does not exist if it exists. This happens at more or less regular
>intervals.

[snip...]

Quote
>Procedure FindNumberI(NumberList:Table;L, R, x:Integer; Var
>INumber:Integer);

>Var
>   m : Integer;

>Begin
>   INumber := 0;
>   While (L < R) do
>      Begin {while}
>         INumber := INumber + 1;
>         m := (L + R) div 2;
>         If NumberList[m] < x then
>            L := m + 1
>         Else
>            R := m;
>      End;  {while}
>      If NumberList[m] = x then

Opps, when the loop has ended you should test

  If NumberList[R] = x Then ...

When L is one less than R and the last test comes in low, then L becomes m+1
breaking the loop.  "m" in this situation is below the "ending" position. If you
study this a little you should see that the ending entry is not m, but r.

    ...red
cc

- Show quoted text -

Quote
>         Writeln('The number ', x, ' exists')
>      Else
>         Writeln('The number ', x, ' does not exist');
>End;

Other Threads