Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > beginner with C : quick search or binary search help needed with forand while

Reply
Thread Tools

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

 
 
bpascal123@googlemail.com
Guest
Posts: n/a
 
      07-01-2009
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[I] = op * 10 / 8 + 6 ;
op = A[I] ;
printf("%4d", A[I]) ;
}

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[I]);
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[I]);
}
printf("Elément à rechercher : ");
scanf("%d", &VAL );

/* Affichage du tableau */

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

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

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

for (I=0 ; (I<N)&&(POS==-1) ; I++)
if (A[I]==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



 
Reply With Quote
 
 
 
 
Morris Keesan
Guest
Posts: n/a
 
      07-02-2009
On Wed, 01 Jul 2009 16:08:04 -0400, http://www.velocityreviews.com/forums/(E-Mail Removed)
<(E-Mail Removed)> wrote:


> 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 */


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[I] = op * 10 / 8 + 6 ;
> op = A[I] ;
> printf("%4d", A[I]) ;
> }


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[i] = op * 10 / 8 + 6;
op = a[i];
printf("%4d", a[i]);
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[I]);


Similarly, this could be written as
i = 0;
while (i < n) {
printf("%d ", a[i]);
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;
> }


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.


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.
 
Reply With Quote
 
 
 
 
James Kuyper
Guest
Posts: n/a
 
      07-02-2009
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.


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

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

is not equivalent to

i = 0; while(i<5) { if(a[i]) 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 ';'.
 
Reply With Quote
 
Nobody
Guest
Posts: n/a
 
      07-02-2009
On Thu, 02 Jul 2009 10:32:20 +0000, James Kuyper 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.

>
> Why do you exclude "continue;" statements? Are you saying
>
> for(i=0; i<5; i++) { if(a[i]) continue;}
>
> is not equivalent to
>
> i = 0; while(i<5) { if(a[i]) continue; i++;}
>
> ?


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[i] 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;
> }
> }


True. But the "continue" issue still applies.

 
Reply With Quote
 
scott
Guest
Posts: n/a
 
      07-02-2009
On Jul 2, 6:32*am, James Kuyper <(E-Mail Removed)> wrote:
> 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.

>
> Why do you exclude "continue;" statements? Are you saying
>
> * * * * *for(i=0; i<5; i++) { if(a[i]) continue;}
>
> is not equivalent to
>
> * * * * *i = 0; while(i<5) { if(a[i]) continue; i++;}
>
> ?

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 ';'.


Your version suffers from the same issue with continue as the other
version. They simply are not the same in that case.
 
Reply With Quote
 
jameskuyper
Guest
Posts: n/a
 
      07-02-2009
Nobody wrote:
> On Thu, 02 Jul 2009 10:32:20 +0000, James Kuyper 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.

> >
> > Why do you exclude "continue;" statements? Are you saying
> >
> > for(i=0; i<5; i++) { if(a[i]) continue;}
> >
> > is not equivalent to
> >
> > i = 0; while(i<5) { if(a[i]) continue; i++;}
> >
> > ?

>
> 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.



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.
 
Reply With Quote
 
bpascal123@googlemail.com
Guest
Posts: n/a
 
      07-02-2009
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[i] = op * 10 / 8 + 6 ;
op = Tab[i] ;
printf("%4d", Tab[i]) ;
}

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 ;
 
Reply With Quote
 
Barry Schwarz
Guest
Posts: n/a
 
      07-03-2009
On Wed, 1 Jul 2009 13:08:04 -0700 (PDT), "(E-Mail Removed)"
<(E-Mail Removed)> wrote:

>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
>===========================================
>


You need to include stdio.h here also.

>main()


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);


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[I] = op * 10 / 8 + 6 ;
> op = A[I] ;
> printf("%4d", A[I]) ;
> }
>
>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[I]);
> printf("\n");


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])


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 )


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 );


You should still check.

>
> for (I=0; I<N; I++)
> {
> printf("Elément %d : ", I);
> scanf("%d", &A[I]);
> }
> printf("Elément à rechercher : ");
> scanf("%d", &VAL );
>
> /* Affichage du tableau */
>
> printf("Tableau donné : \n");
>
> for (I=0; I<N; I++)
> printf("%d ", A[I]);
> printf("\n");
>
> /* Recherche de la position de la valeur */
> POS = -1;
>
> for (I=0 ; (I<N)&&(POS==-1) ; I++)
> if (A[I]==VAL)
> POS=I;


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 )


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.


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

--
Remove del for email
 
Reply With Quote
 
bpascal123@googlemail.com
Guest
Posts: n/a
 
      07-03-2009
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[I]==VAL)
> POS=I;




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...
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      07-03-2009
"(E-Mail Removed)" <(E-Mail Removed)> writes:
> 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


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.


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.

[...]

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Binary tree search vs Binary search Bogdan C Programming 22 10-21-2010 09:46 PM
beginner help with sequential and binary search Ray Leon Java 25 07-12-2008 11:31 PM
Binary Search Tree Vs Quick Sort j1mb0jay Java 5 05-25-2008 12:54 PM
Help understand probems - Binary Search and Sequenital Search Timmy C++ 5 07-09-2007 02:41 PM
Binary Search Tree Help Needed tsunami C++ 3 08-06-2005 07:48 AM



Advertisments