Bonjour,
voici un programme

Si je le compile en C ou en C++, je n'obtiens pas le même
résultat. En C++ fonctionne comme attendu, en C, j'ai un seg fault
(runtime error)
Voyez-vous une raison ?
Cordialement,
David


#include <stdio.h>

int Max( int i, int j ) { return ( i > j ? i : j ); }
int Min( int i, int j ) { return ( i < j ? i : j ); }

int CycleLength( int n ) {
int cycleLength = 1;
while ( n != 1 ) {
if ( n &0x01 ) n = 3*n + 1;
else n >>= 1;
++cycleLength;
}
return cycleLength;
}

int maxCycle( int i, int j ){
int max = CycleLength( i++ );
for( ;i <= j; ++i )
max = Max( max, CycleLength( i ) );
return max;
}

int main()
{
int i, j;
while( fscanf(stdin, "%d %d\n", &i, &j ) == 2 )
fprintf(stdout, "%d %d %d\n", i, j ,
maxCycle( Min(i,j), Max(i,j) ));
}

On Thu, 10 Apr 2008 22:55:08 +0200, David Fleury
<dfleury2@libertysurf.fr>:

>Si je le compile en C ou en C++, je n'obtiens pas le même
>résultat. En C++ fonctionne comme attendu, en C, j'ai un seg fault
>(runtime error)

Je n'arrive pas à trouver de problème dans le code. Quel compilateur
utilises-tu, et quelles options de compilation ?

> int max = CycleLength( i++ );

En théorie, max() est bien une fonction, et ça ne pose pas de
problème. Mais en pratique, il arrive que ce soit une macro, aussi je
déconseille de donner ce nom à une variable.

J'ai pour habitude d'appeler "reponse" la variable renvoyée par une
fonction :

int f()
{
int reponse= 3;
reponse+= 39;
return reponse;
}

Fabien LE LEZ a écrit :
> On Thu, 10 Apr 2008 22:55:08 +0200, David Fleury
> <dfleury2@libertysurf.fr>:
>
>> Si je le compile en C ou en C++, je n'obtiens pas le même
>> résultat. En C++ fonctionne comme attendu, en C, j'ai un seg fault
>> (runtime error)
>
> Je n'arrive pas à trouver de problème dans le code. Quel compilateur
> utilises-tu, et quelles options de compilation ?
>

gcc 4.1.2 -lm -lcrypt -O2 -pipe -ansi
et
g+++ -lm -lcrypt -O2 -pipe

en fait, ce code est censé répondre à un des problèmes d'un site
de problème d'algo. Pour le moment, je ne leur ai pas demandé
de regarder de leur côté. Je voulais d'abord un avis extérieur
n'ayant rien trouvé à redire de mon côté sur un programme aussi simple.

>> int max = CycleLength( i++ );
>
> En théorie, max() est bien une fonction, et ça ne pose pas de
> problème. Mais en pratique, il arrive que ce soit une macro, aussi je
> déconseille de donner ce nom à une variable.

oui, en effet, le nom est mal venu ici


> J'ai pour habitude d'appeler "reponse" la variable renvoyée par une
> fonction :
>
> int f()
> {
> int reponse= 3;
> reponse+= 39;
> return reponse;
> }
>

In article <47ff05e8$0$746$426a74cc@news.free.fr>,
David Fleury <dfleury2@libertysurf.fr> wrote:
>Fabien LE LEZ a écrit :
>> On Thu, 10 Apr 2008 22:55:08 +0200, David Fleury
>> <dfleury2@libertysurf.fr>:
>>
>>> Si je le compile en C ou en C++, je n'obtiens pas le même
>>> résultat. En C++ fonctionne comme attendu, en C, j'ai un seg fault
>>> (runtime error)
>>
>> Je n'arrive pas à trouver de problème dans le code. Quel compilateur
>> utilises-tu, et quelles options de compilation ?
>>
>
>gcc 4.1.2 -lm -lcrypt -O2 -pipe -ansi
>et
>g+++ -lm -lcrypt -O2 -pipe
>
>en fait, ce code est censé répondre à un des problèmes d'un site
>de problème d'algo. Pour le moment, je ne leur ai pas demandé
>de regarder de leur côté. Je voulais d'abord un avis extérieur
>n'ayant rien trouvé à redire de mon côté sur un programme aussi simple.

Juste pour info, ca n'est pas un vrai `probleme d'algo'. La recurrence
indiquee s'appelle la `conjecture de Syracuse', et personne n'a jamais
reussi a la prouver.

La conjecture pose la recurrence suivante partant de u_0:

si u_n est pair, u_n+1 = u_n / 2
si u_n est impair, u_n+1 = u_n * 3 + 1

et postule que la suite u_n finit toujours par rejoindre
4 2 1 4 2 1 4 2 1 ...

ca a ete verifie experimentalement jusqu'a des valeurs tres importantes,
mais aucune preuve n'en est jamais sorti.

Classer les entiers selon le nombre d'etapes necessaires pour rejoindre
4 2 1 ... peut sembler une bonne premiere etape. A ma connaissance, on n'a
vraiment tres peu de renseignements la-dessus.

David Fleury <dfleury2@libertysurf.fr> writes:

> Bonjour,
> voici un programme
>
> Si je le compile en C ou en C++, je n'obtiens pas le même
> résultat. En C++ fonctionne comme attendu, en C, j'ai un seg fault
> (runtime error)
> Voyez-vous une raison ?
> Cordialement,
> David
> [...]
> if ( n &0x01 ) n = 3*n + 1;
> [...]

Tu rêves mon gars, c'est pas du lisp!

------------------------------------------------------------------------
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int Max( int i, int j ) { return ( i > j ? i : j ); }
int Min( int i, int j ) { return ( i < j ? i : j ); }

int CycleLength( int n ) {
int original=n;
int cycleLength = 1;
while ( n != 1 ) {
if ( n &0x01 ){
if(n<((INT_MAX-1)/3)){
n = 3*n + 1;
}else{
fprintf(stderr,"Arithemtic overflow on %d\n",original);
exit(1);
}
}else{
n >>= 1;
}
++cycleLength;
}
return cycleLength;
}

int maxCycle( int i, int j ){
int max = CycleLength( i++ );
for( ;i <= j; ++i )
max = Max( max, CycleLength( i ) );
return max;
}

int main()
{
int i, j;
while( fscanf(stdin, "%d %d\n", &i, &j ) == 2 )
fprintf(stdout, "%d %d %d\n", i, j ,
maxCycle( Min(i,j), Max(i,j) ));
}

------------------------------------------------------------------------
Ce qui donne, en 32-bit:
echo 1 10000000|./syracuse-c
Arithemtic overflow on 113383


--
__Pascal Bourguignon__

On Fri, 11 Apr 2008 10:41:55 +0200, pjb@informatimago.com (Pascal J.
Bourguignon):

>Ce qui donne, en 32-bit:
>echo 1 10000000|./syracuse-c
>Arithemtic overflow on 113383

Arf, effectivement, je n'y avais même pas pensé.
Par contre, je ne comprends pas pourquoi le programme plante. n*3+1
devrait donner une valeur (éventuellement fausse au sens arithmétique)
pour tout n, sans plantage, non ?

Fabien LE LEZ a écrit :
> Par contre, je ne comprends pas pourquoi le programme plante. n*3+1
> devrait donner une valeur (éventuellement fausse au sens arithmétique)
> pour tout n, sans plantage, non ?

Ce n'est pas pour rien que le compilateur et la plate-forme cible
t'ont été demandé(es ?).

--
Mickaël Wolff aka Lupus Michaelis
http://lupusmic.org

Fabien LE LEZ <gramster@gramster.com> writes:

> On Fri, 11 Apr 2008 10:41:55 +0200, pjb@informatimago.com (Pascal J.
> Bourguignon):
>
>>Ce qui donne, en 32-bit:
>>echo 1 10000000|./syracuse-c
>>Arithemtic overflow on 113383
>
> Arf, effectivement, je n'y avais même pas pensé.
> Par contre, je ne comprends pas pourquoi le programme plante. n*3+1
> devrait donner une valeur (éventuellement fausse au sens arithmétique)
> pour tout n, sans plantage, non ?

Non, les débordement peuvent produire n'importe quel résultat, comme
le déclanchement de la quatrième guerre mondiale, ou la sortie de
démons nasaux. En clair, chaque compilateur fait ce qu'il veut.

--
__Pascal Bourguignon__

Fabien LE LEZ a écrit :
> On Fri, 11 Apr 2008 10:41:55 +0200, pjb@informatimago.com (Pascal J.
> Bourguignon):
>
>> Ce qui donne, en 32-bit:
>> echo 1 10000000|./syracuse-c
>> Arithemtic overflow on 113383
>
> Arf, effectivement, je n'y avais même pas pensé.
> Par contre, je ne comprends pas pourquoi le programme plante. n*3+1
> devrait donner une valeur (éventuellement fausse au sens arithmétique)
> pour tout n, sans plantage, non ?
>

J'ai pas précisé ce point...

"You can assume that no operation overflows a 32-bit integer."

les nombres en entrée sont inclut entre 1 et 1.000.000
(ce qui n'empêche pas le dépassement de toute façon)

Marc Espie a écrit :
> In article <47ff05e8$0$746$426a74cc@news.free.fr>,
>
> Juste pour info, ca n'est pas un vrai `probleme d'algo'. La recurrence
> indiquee s'appelle la `conjecture de Syracuse', et personne n'a jamais
> reussi a la prouver.
>
> La conjecture pose la recurrence suivante partant de u_0:
>
> si u_n est pair, u_n+1 = u_n / 2
> si u_n est impair, u_n+1 = u_n * 3 + 1
>
> et postule que la suite u_n finit toujours par rejoindre
> 4 2 1 4 2 1 4 2 1 ...
>
> ca a ete verifie experimentalement jusqu'a des valeurs tres importantes,
> mais aucune preuve n'en est jamais sorti.
>
> Classer les entiers selon le nombre d'etapes necessaires pour rejoindre
> 4 2 1 ... peut sembler une bonne premiere etape. A ma connaissance, on n'a
> vraiment tres peu de renseignements la-dessus.

En fait, ce problème est là plutôt pour se familiariser avec l'interface
de soumission avec un problème simple.
Une sorte de tutorial, le résoudre n'est pas le but ici.

Pascal J. Bourguignon a écrit :
> Fabien LE LEZ <gramster@gramster.com> writes:
>
>> On Fri, 11 Apr 2008 10:41:55 +0200, pjb@informatimago.com (Pascal J.
>> Bourguignon):
>>
>>> Ce qui donne, en 32-bit:
>>> echo 1 10000000|./syracuse-c
>>> Arithemtic overflow on 113383
>> Arf, effectivement, je n'y avais même pas pensé.
>> Par contre, je ne comprends pas pourquoi le programme plante. n*3+1
>> devrait donner une valeur (éventuellement fausse au sens arithmétique)
>> pour tout n, sans plantage, non ?
>
> Non, les débordement peuvent produire n'importe quel résultat, comme
> le déclanchement de la quatrième guerre mondiale, ou la sortie de
> démons nasaux. En clair, chaque compilateur fait ce qu'il veut.
>

J'étais étonné de la différence pour le même oss, le même code,
et un compilo différent.

Ce qui m'embête toujours un peu , c'est qu'en utilisant le code
vérifiant la dépassement (un remplaçant exit(1) par exit(0)), je devrais
juste avoir une "mauvaise réponse", mais j'obtiens toujours une erreur.

David Fleury <dfleury2@libertysurf.fr> writes:

> Pascal J. Bourguignon a écrit :
>> Fabien LE LEZ <gramster@gramster.com> writes:
>>
>>> On Fri, 11 Apr 2008 10:41:55 +0200, pjb@informatimago.com (Pascal J.
>>> Bourguignon):
>>>
>>>> Ce qui donne, en 32-bit:
>>>> echo 1 10000000|./syracuse-c
>>>> Arithemtic overflow on 113383
>>> Arf, effectivement, je n'y avais même pas pensé.
>>> Par contre, je ne comprends pas pourquoi le programme plante. n*3+1
>>> devrait donner une valeur (éventuellement fausse au sens arithmétique)
>>> pour tout n, sans plantage, non ?
>> Non, les débordement peuvent produire n'importe quel résultat, comme
>> le déclanchement de la quatrième guerre mondiale, ou la sortie de
>> démons nasaux. En clair, chaque compilateur fait ce qu'il veut.
>>
>
> J'étais étonné de la différence pour le même oss, le même code,
> et un compilo différent.
>
> Ce qui m'embête toujours un peu , c'est qu'en utilisant le code
> vérifiant la dépassement (un remplaçant exit(1) par exit(0)), je
> devrais
> juste avoir une "mauvaise réponse", mais j'obtiens toujours une erreur.

Alors là, je ne sais pas. Essaye d'exécuter le programme sous gdb et
voir où exactement se situe l'erreur.

--
__Pascal Bourguignon__ http://www.informatimago.com/

WARNING: This product attracts every other piece of matter in the
universe, including the products of other manufacturers, with a
force proportional to the product of the masses and inversely
proportional to the distance between them.