beginner with C : quick search or binary search help needed with forand while

B

bpascal123

Hi,

I'd like to know how to use well FOR et WHILE. I post this script
below so to illustrate a quicksort program :

1st : it doesn't work

2nd : I 'd like to see how to replace for by while or while by for ---
for that specific program (I couldn't figure this out altough I spent
a lot of time on this - but the programm I'm doing so from is not even
fully working, I made it work once by changing variable POS :

Everything below ( plz don't include functions, for the time i'm
spending to learn, i'd like to deepen my knowledge of basic structures
and arrays...)


===========================================
START HERE
===========================================

main()
{
/* Déclarations */
int A[50]; /* table */
int VAL; /* value */
int POS; /* position */
int N; /* dimension */
int I; /* indice courant */
int INF, MIL, SUP; /* limits */


printf("\n\n===============\n\n") ;

printf("How many numbers in the array ? ") ;
scanf("%d", &N);

for (I=0; I<N; I++)
{
A = op * 10 / 8 + 6 ;
op = A ;
printf("%4d", A) ;
}

printf("\n\n===============\n\n") ;


printf("Enter a number you are looking for : ");
scanf("%d", &VAL );

/* Display the array */

printf("Array entered is : \n");

for (I=0; I<N; I++)
printf("%d ", A);
printf("\n");

/* Set search limits*/

INF=0;
SUP=N-1;

/* Search the number */

POS=-1;

while ((INF<=SUP) && (POS==-1))
{
MIL=(SUP+INF)/2;
if (VAL < A[MIL])
SUP=MIL-1;
else if (VAL > A[MIL])
INF=MIL+1;
else
POS=MIL;
}

/* Print the result of the search */

if (POS==-1)
printf("No match\n");
else
printf("Value is %d and its position %d. \n",
VAL, POS);

return 0;
===========================================
ENDS HERE ( with the last "main" bracket )
===========================================


Below it the same one but fully working (i didn't translate it as
variables remain the same)


===========================================
START HERE
===========================================

#include <stdio.h>
main()
{
/* Déclarations */
int A[50]; /* tableau donné */
int VAL; /* valeur à rechercher */
int POS; /* position de la valeur */
int N; /* dimension */
int I; /* indice courant */

/* Saisie des données */

printf("Dimension du tableau (max.50) : ");
scanf("%d", &N );

for (I=0; I<N; I++)
{
printf("Elément %d : ", I);
scanf("%d", &A);
}
printf("Elément à rechercher : ");
scanf("%d", &VAL );

/* Affichage du tableau */

printf("Tableau donné : \n");

for (I=0; I<N; I++)
printf("%d ", A);
printf("\n");

/* Recherche de la position de la valeur */
POS = -1;

for (I=0 ; (I<N)&&(POS==-1) ; I++)
if (A==VAL)
POS=I;

/* Edition du résultat */

if (POS==-1)
printf("La valeur recherchée ne se trouve pas "
"dans le tableau.\n");
else
printf("La valeur %d se trouve à la position %d. \n",
VAL, POS);

return 0;

===========================================
ENDS HERE ( with the last "main" bracket )
===========================================

Please focus your help just on FOR and WHILE, so far I can't deal with
ANSI or NON ANSI issues for scanf and so on as I'd really like to
first understand such easy loop which I think are essentials.

Many thanks if you can take me out of that :

Pascal
 
M

Morris Keesan

main()
{
/* Déclarations */
int A[50]; /* table */
int VAL; /* value */
int POS; /* position */
int N; /* dimension */
int I; /* indice courant */
int INF, MIL, SUP; /* limits */
Click to expand...

Don't do this (variable names in ALL UPPER CASE). It will confuse any
other
C programmer trying to read your code, and if you get used to it, it will
make
it much harder for you to read others' code. Although it's legal in the
language, by convention variable names in C are either in all lower-case,
or in some communities in camelCase (i.e. if a variable name consists of
multiple words, some programmers capitalize the beginnings of the second
and
subsequent words. Others insert underscores).
printf("\n\n===============\n\n") ;

printf("How many numbers in the array ? ") ;
scanf("%d", &N);

for (I=0; I<N; I++)
{
A = op * 10 / 8 + 6 ;
op = A ;
printf("%4d", A) ;
}
Click to expand...


In the code you've posted, you've neglected to declare the variable op, and
it has no initial value. Assuming a declaration with initialization for
op,
you can convert this "for" loop to the equivalent "while" loop (with
variable
names downcased):

i = 0;
while (i < n)
{
a = op * 10 / 8 + 6;
op = a;
printf("%4d", a);
i++;
}

The general rule is that

for (initialization; test; increment) { body; }

is equivalent to

initialization; while(test) { body; increment }

except where "body;" contains any "continue" statements.

for (I=0; I<N; I++)
printf("%d ", A);
Click to expand...


Similarly, this could be written as
i = 0;
while (i < n) {
printf("%d ", a);
i++;
}

POS=-1;

while ((INF<=SUP) && (POS==-1))
{
MIL=(SUP+INF)/2;
if (VAL < A[MIL])
SUP=MIL-1;
else if (VAL > A[MIL])
INF=MIL+1;
else
POS=MIL;
}
Click to expand...

and if you wanted to replace this while loop with a for loop, it would be

for (pos = -1; (inf <= sup) && (pos == -1); /* no expression here */)
{
/* body of for same as body of while */
}

Please focus your help just on FOR and WHILE, so far I can't deal with
ANSI or NON ANSI issues for scanf and so on as I'd really like to
first understand such easy loop which I think are essentials.
Click to expand...

I haven't bothered trying to read your program enough to figure out the
logic or the algorithms in use. These are just conversions of one loop
type
to another. I would say that the loop forms you've used are those that
most
C programmers would use. I can't think of a reason why anyone would want
to use
while loops where you've used for loops, or vice versa.
 
J

James Kuyper

Morris Keesan wrote:
....
The general rule is that

for (initialization; test; increment) { body; }

is equivalent to

initialization; while(test) { body; increment }

except where "body;" contains any "continue" statements.
Click to expand...

Why do you exclude "continue;" statements? Are you saying

for(i=0; i<5; i++) { if(a) continue;}

is not equivalent to

i = 0; while(i<5) { if(a) continue; i++;}

?

A more accurate equivalent would be to say that

for(initialization; test; increment) BODY

is equivalent to

{
initialization;
while(test)
{
BODY;
increment;
}
}

This adds the terminating ';' to 'increment' that was missing from your
version. It also uses curly brackets '{' and '}' to more accurately
represent the restricted scope of any identifier declared in
'initialization'. This introduces a spurious extra level of nesting, but
is otherwise correct.

Most importantly, my formulation is more general, because I'm using BODY
to represent a single statement of any type; if it's a compound
statement, BODY includes the '{' and '}' characters. If it's a selection
or iteration statement, it includes the associated keywords (if, else,
for, do, while). If it's any other kind of statement, it includes the
terminating ';'.
 
N

Nobody

The general rule is that

for (initialization; test; increment) { body; }

is equivalent to

initialization; while(test) { body; increment }

except where "body;" contains any "continue" statements.
Click to expand...

Why do you exclude "continue;" statements? Are you saying

for(i=0; i<5; i++) { if(a) continue;}

is not equivalent to

i = 0; while(i<5) { if(a) continue; i++;}

?
Click to expand...


Correct. The increment part of a "for" statement is executed for each pass
of the loop, regardless of whether the loop body completes normally or is
terminated prematurely by a "continue". With the "while" version, a
"continue" will skip the increment.

In your example, if any a is non-zero, the loop will never terminate.
A more accurate equivalent would be to say that

for(initialization; test; increment) BODY

is equivalent to

{
initialization;
while(test)
{
BODY;
increment;
}
}
Click to expand...

True. But the "continue" issue still applies.
 
S

scott

Morris Keesan wrote:

...
The general rule is that
Click to expand...
    for (initialization; test; increment) { body; }
Click to expand...
is equivalent to
Click to expand...
    initialization; while(test) { body; increment }
Click to expand...
except where "body;" contains any "continue" statements.
Click to expand...

Why do you exclude "continue;" statements? Are you saying

         for(i=0; i<5; i++) { if(a) continue;}

is not equivalent to

         i = 0; while(i<5) { if(a) continue; i++;}

?
Click to expand...

They are not equivalent. In the second case when the continue is hit
the increment will not happen which means you will have yourself stuck
in an infinite loop.
A more accurate equivalent would be to say that

        for(initialization; test; increment) BODY

is equivalent to

         {
              initialization;
              while(test)
              {
                   BODY;
                   increment;
              }
         }

This adds the terminating ';' to 'increment' that was missing from your
version. It also uses curly brackets '{' and '}' to more accurately
represent the restricted scope of any identifier declared in
'initialization'. This introduces a spurious extra level of nesting, but
is otherwise correct.

Most importantly, my formulation is more general, because I'm using BODY
to represent a single statement of any type; if it's a compound
statement, BODY includes the '{' and '}' characters. If it's a selection
or iteration statement, it includes the associated keywords (if, else,
for, do, while). If it's any other kind of statement, it includes the
terminating ';'.
Click to expand...

Your version suffers from the same issue with continue as the other
version. They simply are not the same in that case.
 
J

jameskuyper

Nobody said:
The general rule is that

for (initialization; test; increment) { body; }

is equivalent to

initialization; while(test) { body; increment }

except where "body;" contains any "continue" statements.
Click to expand...

Why do you exclude "continue;" statements? Are you saying

for(i=0; i<5; i++) { if(a) continue;}

is not equivalent to

i = 0; while(i<5) { if(a) continue; i++;}

?
Click to expand...


Correct. The increment part of a "for" statement is executed for each pass
of the loop, regardless of whether the loop body completes normally or is
terminated prematurely by a "continue". With the "while" version, a
"continue" will skip the increment.
Click to expand...



You're right, and I should have realized it. I'm beginning to wonder
whether it's worthwhile posting newsgroup messages before I've fully
woken up in the morning.
 
B

bpascal123

Hi all,

Below is a version with For I have worked out but it's not working.

I didn't translate any lines of code but i can tell you basically what
the program expects :

- it first asks to enter a number which will be taken as the number of
values in the array ;

- then it displays an array of numbers and afterwards asks for a value
and checks (with FOR) the position of the value in the array (i didn't
make any controls with if to see if the value either exists or not, I
am just focusing on making this script work---caps lock corrections
and controls with "if" will come right next)

But as you can, its position is not right at all.

Could you correct it please?

Thanks in advance

Pascal


#include <stdio.h>

main()
{
int Tab[50] ;
int N ;
int MIL, INF, SUP ;
int VAL ;
int POS ;
int midPOS ;
int op ;
int i, j ;
int cnt = 1 ;
int permut1 ;
int ECRI ;

printf("\n\n==============================\n\n") ;

printf("Ce prg lit, affiche un tableau et y recherche une valeur et
sa position.") ;

printf("\n\n===============\n\n") ;

printf("Entrez le nbr de valeurs : ") ;
scanf("%d", &N);

for ( i = 0 ; i < N ; i++ )
{
Tab = op * 10 / 8 + 6 ;
op = Tab ;
printf("%4d", Tab) ;
}

printf("\n\n===============\n\n") ;


printf("Entrez une valeur a rechercher : \n\n") ;
scanf("%d", &VAL ) ;

printf("\n\n") ;


INF = 0 ; SUP = N - 1 ;

for ( INF = 0 ; INF <= SUP ; INF++ )
{
MIL=(SUP+INF)/2;

if ( VAL < Tab[MIL] )
POS = MIL - 1 ;

else if ( VAL > Tab[MIL] )
POS = MIL + 1 ;
else
POS = MIL ;
ECRI = SUP + INF ;
}

printf("\n\n===============\n\n") ;

printf("Tri : la position est %d . ===> %d ", POS, MIL ) ;


printf("\n\n==============================\n\n") ;

return 0 ;
 
B

Barry Schwarz

Hi,

I'd like to know how to use well FOR et WHILE. I post this script
below so to illustrate a quicksort program :

1st : it doesn't work

2nd : I 'd like to see how to replace for by while or while by for ---
for that specific program (I couldn't figure this out altough I spent
a lot of time on this - but the programm I'm doing so from is not even
fully working, I made it work once by changing variable POS :

Everything below ( plz don't include functions, for the time i'm
spending to learn, i'd like to deepen my knowledge of basic structures
and arrays...)


===========================================
START HERE
===========================================
Click to expand...

You need to include stdio.h here also.
main()
Click to expand...

use int main(void). Implied return of int has been removed from the
language even though many compilers still support it.
{
/* Déclarations */
int A[50]; /* table */
int VAL; /* value */
int POS; /* position */
int N; /* dimension */
int I; /* indice courant */
int INF, MIL, SUP; /* limits */


printf("\n\n===============\n\n") ;

printf("How many numbers in the array ? ") ;
scanf("%d", &N);
Click to expand...

If you are going to let the use specify, you better make sure he
specifies 50 or less.
for (I=0; I<N; I++)
{
A = op * 10 / 8 + 6 ;
op = A ;
printf("%4d", A) ;
}

printf("\n\n===============\n\n") ;


printf("Enter a number you are looking for : ");
scanf("%d", &VAL );

/* Display the array */

printf("Array entered is : \n");

for (I=0; I<N; I++)
printf("%d ", A);
printf("\n");
Click to expand...


How does this differ from the previous for loop?
/* Set search limits*/

INF=0;
SUP=N-1;

/* Search the number */

POS=-1;

while ((INF<=SUP) && (POS==-1))
{
MIL=(SUP+INF)/2;
if (VAL < A[MIL])
Click to expand...

A binary search is only useful is the array is sorted.
SUP=MIL-1;
else if (VAL > A[MIL])
INF=MIL+1;
else
POS=MIL;
}

/* Print the result of the search */

if (POS==-1)
printf("No match\n");
else
printf("Value is %d and its position %d. \n",
VAL, POS);

return 0;
===========================================
ENDS HERE ( with the last "main" bracket )
Click to expand...

Where is the bracket (actually called a brace)?
===========================================


Below it the same one but fully working (i didn't translate it as
variables remain the same)


===========================================
START HERE
===========================================

#include <stdio.h>
main()
{
/* Déclarations */
int A[50]; /* tableau donné */
int VAL; /* valeur à rechercher */
int POS; /* position de la valeur */
int N; /* dimension */
int I; /* indice courant */

/* Saisie des données */

printf("Dimension du tableau (max.50) : ");
scanf("%d", &N );
Click to expand...

You should still check.
for (I=0; I<N; I++)
{
printf("Elément %d : ", I);
scanf("%d", &A);
}
printf("Elément à rechercher : ");
scanf("%d", &VAL );

/* Affichage du tableau */

printf("Tableau donné : \n");

for (I=0; I<N; I++)
printf("%d ", A);
printf("\n");

/* Recherche de la position de la valeur */
POS = -1;

for (I=0 ; (I<N)&&(POS==-1) ; I++)
if (A==VAL)
POS=I;
Click to expand...


This is a sequential search and is insensitive to the order of the
values.
/* Edition du résultat */

if (POS==-1)
printf("La valeur recherchée ne se trouve pas "
"dans le tableau.\n");
else
printf("La valeur %d se trouve à la position %d. \n",
VAL, POS);

return 0;

===========================================
ENDS HERE ( with the last "main" bracket )
Click to expand...

Why do you omit the brace? If anyone wants to compile your code, the
don't want to bother fixing syntax errors.
===========================================

Please focus your help just on FOR and WHILE, so far I can't deal with
ANSI or NON ANSI issues for scanf and so on as I'd really like to
first understand such easy loop which I think are essentials.
Click to expand...

I'm not aware of any ASCII/non-ASCII issues for %d.
 
B

bpascal123

If you are going to let the use specify, you better make sure he
specifies 50 or less.

Yes, this is done in the printf cmd...


A binary search is only useful is the array is sorted.

This array is already sorted from the smallest to the greatest value.
If it wouldn't be the case, I would insert a "permuting" loop


Where is the bracket (actually called a brace)?

When I copy-paste in google group usenet, the bracket is deleted by
the browser, i think it's a security issue.

for (I=0 ; (I<N)&&(POS==-1) ; I++)
if (A==VAL)
POS=I;
Click to expand...




This is a sequential search and is insensitive to the order of the
values.


I know about this sequential search, but it would take in a huge
database that's why I'd like to understand how to make search from the
middle by comparing the mid value with the value being searched and
then do a sequential search...I had thought it's part of the basics
for any programers...
 
K

Keith Thompson

[email protected] said:
If you are going to let the use specify, you better make sure he
specifies 50 or less.

Yes, this is done in the printf cmd...


A binary search is only useful is the array is sorted.

This array is already sorted from the smallest to the greatest value.
If it wouldn't be the case, I would insert a "permuting" loop
Click to expand...

About half of the above is actually quoted from a previous article
by Barry Schwarz, but the quotations aren't marked in any way.

The Google Groups interface will actually include the article you're
responding to, properly quoted. Please don't override that
feature.
Where is the bracket (actually called a brace)?

When I copy-paste in google group usenet, the bracket is deleted by
the browser, i think it's a security issue.
Click to expand...

That's implausible. Google Groups users manage to copy-and-paste C
code all the time, and I've never seen a problem with curly braces.
You probably just didn't copy-and-paste the entire program.
Mistakes happen, and they aren't a huge deal.

[...]
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Beginner at c 0
Problem with do while 2
Need help in debugging tic tac toe (Beginner) 0
Need help in debugging tic tac toe (beginner) 2
Using Do-While loop statement for a selection Menu 3
Please help with C programming to save GPS reception data in Raspberry Pi. 0
Help! (Beginner) 2
Filter sober in c++ don't pass test 0

Members online

No members online now.
Total: 30 (members: 0, guests: 30)
Robots: 236

Forum statistics

Threads
473,763
Messages
2,569,563
Members
45,039
Latest member
CasimiraVa

Latest Threads

Top