Quelques avis :
- l'utilisation des fonctions d'entrée/sortie n'est pas intéressante. Moins il y en a, mieux on se porte.
- de même, l'utilisation des fonctions système n'a pas grand intérêt en général (on risque d'avoir des problèmes de portabilité, et c'est chiant à coder)

Idées d'exercice (qui violent une partie des points cités) :
- écrire une fonction qui permute aléatoirement les éléments d'un tableau (et uniformément, c'est à dire que chaque disposition finale a autant de chance que les autres d'être choisie)
- écrire un Quine, c'est à dire un programme qui affiche son propre code source quand on l'exécute
- écrire une bibliothèque permettant d'ajouter et de retirer des éléments en début et en fin de liste (structure de donnée définie dans la bibliothèque)
- écrire une fonction qui prend une chaine de caractères en entrée, et indique si elle est bien parenthésée (à chaque parenthèse ouvrante correspond une parenthèse fermante, elles sont bien imbriquées, etc.)
- écrire une fonction qui prend deux entiers (n,p), et répond à la question suivante : un cavalier peut-il parcourir entièrement un échiquier de n cases de longueur et p cases de largeur, sans repasser deux fois par la même case ?
- même question en donnant un chemin qui convient, s'il existe

bonjour,
merci Eusebus pour avoir repris le flambeau, et proposé un nouvel exercice.
Voici ma solution personnelle avec un peu de retard !

j'ai pris comme solution , une chaine de caracteres à traiter, par contre il est vrai j'ai différencié tous les caracteres alphanumériques de la table ASCII.
@+

Ta solution est très lente (tu fais un parcours de la chaîne par lettre). Je t'invite à lire ma proposition.

bonjour

Citation : bluestorm

Ta solution est très lente (tu fais un parcours de la chaîne par lettre). Je t'invite à lire ma proposition.

merci pour ta remarque bluestorm. Effectivement j'ai choisi un parcours de la chaine lettre par lettre. Sauf que je comprends pas comment faire autrement, ton explication n'est pas claire dans mon petit cerveau !
Merci
@+

Citation : bluestorm

- écrire une fonction qui permute aléatoirement les éléments d'un tableau (et uniformément, c'est à dire que chaque disposition finale a autant de chance que les autres d'être choisie)

Ça me parait être une bonne idée d'exercice en effet.

Citation : bluestorm

- écrire un Quine, c'est à dire un programme qui affiche son propre code source quand on l'exécute

Est-tu sûr que c'est aussi facile que tu le dit? (sauf bien sûr si le programme ne fait que lire le fichier main.c et l'afficher)

Citation : bluestorm

- écrire une fonction qui prend deux entiers (n,p), et répond à la question suivante : un cavalier peut-il parcourir entièrement un échiquier de n cases de longueur et p cases de largeur, sans repasser deux fois par la même case ?

Cet exercice peut être intéressant lui aussi.

Citation

Est-tu sûr que c'est aussi facile que tu le dit? (sauf bien sûr si le programme ne fait que lire le fichier main.c et l'afficher)

Non, c'est pas facile (surtout en C qui a des contraintes syntaxiques un peu plus chiante que mon langage habituel, Caml), mais on peut le faire en ayant lu le cours de C de M@teo, et ça n'est pas plus facile pour les gens "avertis" qui ne se sont pas posé la question.

Je viens de coder une solution (et non on ne lit pas le fichier main.c, ça marche même si on change le nom de la source), ça n'a pas été évident mais c'est drôle à faire.


Edit : il existe aussi de nombreuses solutions sur internet qui sont sûrement beaucoup mieux que la mienne, mais je vous déconseille de les chercher si la solution vous intéresse (pourtant j'ai donné le mot clé : Quine), car une fois qu'on en a lue, on n'a plus le plaisir de se dire "je l'ai trouvé tout seul", et on s'en veut toute sa vie, ou pas.

Citation : zx-spectrum

Effectivement j'ai choisi un parcours de la chaine lettre par lettre. Sauf que je comprends pas comment faire autrement, ton explication n'est pas claire dans mon petit cerveau !

Pour chaque caractère ASCII, tu parcours l'ensemble de la chaîne, si tu as donc n caractères, tu feras 256*n "opérations". Ton algorithme est donc en O(256n). L'algorithme de bluestorm est différent : il parcours une fois la chaîne (O(n) ) et caractère après caractère, il réalise un comptage (voir tri comptage pour mieux comprendre ce principe). À la fin, il parcours le tableau contenant l'histogramme résultant du comptage et affiche les effectifs. L'algo n'est pas vraiment en O(n), il est exactement en O(n+256), mais là, on peut simplifier en O(n), le 256 ne variant pas. En pratique, le tri comptage réalise un histogramme de la valeur la plus inférieure à la valeur la plus supérieure, il est donc en O(N+max-min).

Edit : corrigé, j'avais mal compris l'algo de zx.

Citation : bluestorm

je vous déconseille de les chercher si la solution vous intéresse (pourtant j'ai donné le mot clé : Quine), car une fois qu'on en a lue, on n'a plus le plaisir de se dire "je l'ai trouvé tout seul", et on s'en veut toute sa vie, ou pas.

Oui, ça me ferait chier en effet. J'ai planché dessus 20 minutes mais sans succès.
Franchement je dois dire que je ne sais pas comment faire.

ShareMan : pour mieux observer la différence entre ces deux algorithmes, tu peux considérer la taille de l'alphabet (ici 256) comme une variable A. Son algorithme est en O(N*A), avec une complexité mémoire (si on considère la chaîne initiale déjà allouée) O(1), et le mien est en O(N), ou plus exactement O(N+A) (allocation du tableau), avec une complexité mémoire en O(A).

Merci Shareman, bluestorm pour vos precisions, je vais revoir ma copie pour parcourir en fait une fois ma chaine à traiter!
@+

Citation : bluestorm

- écrire une fonction qui prend deux entiers (n,p), et répond à la question suivante : un cavalier peut-il parcourir entièrement un échiquier de n cases de longueur et p cases de largeur, sans repasser deux fois par la même case ?
- même question en donnant un chemin qui convient, s'il existe

Je n'ai surement pas le niveau pour faire ça, plus tard j'essayerai surement.
Faut il tenir compte avec le fait qu'un cavalier part toujours à 2 cases de la fin de la largeur.
Ainsi sur un échiquier si il y a 8*8 cases le cavalier se trouve sur la 6 ème case.
Je sais pas si il faut en tenir compte où si on peut le aire partir de n'importe quel endroit.

Tu peux partir de n'importe quel endroit. Par exemple (0,0). Empiriquement, j'ai observé que dans la plupart des cas, ça ne dépend en fait pas de la case de départ.

Citation : bluestorm

Tu peux partir de n'importe quel endroit. Par exemple (0,0). Empiriquement, j'ai observé que dans la plupart des cas, ça ne dépend en fait pas de la case de départ.

A mon avis c'est :

Il s'agit de trouver un algorithme qui donne la solution, en cherchant un chemin qui convient.

Ta réponse est fausse. D'une part, ça ne marche pas sur un échiquier de taille 1x3 (ils ne sont pas forcément carrés) ou 3x3, donc il ne s'agit pas de divisibilité par 3 (ou pas uniquement). D'ailleurs ça marche sur un échiquier classique 8x8, qui ne satisfait pas ta condition.
D'autre part, dans un mouvement du cavalier on considère seulement la case de départ et la case d'arrivée. Le cavalier "saute" et on ne compte pas les cases entre les deux comme utilisées.

à quand le prochain exo?

Pas mal les propositions d'exercices. Surtout le Quine. Je n'avais jamais pensé à un exercice de ce genre et je ne voie pas comment le faire sans lire directement le main.cpp

Est-ce que on a le droit de lire la Makefile (pour connaître les sources) ?

Ma solution utilise des fonctions d'affichage (dans mon cas putc et fputs, mais on peut sans doute utiliser printf à la place), rien d'autre.

Je ne dis pas que tout le monde doit faire pareil (même si en fait, un peu quand même), mais on peut s'en sortir "à la loyale" sans utiliser ce genre d'astuces plus ou moins mauvaises (la tienne étant dans le plus : qui te dit qu'il y a un Makefile ?).

Franchement je dois dire que tu me pose une colle, j'ai planché dessus plusieurs heures hier soir sans résultat. Je ne dois pas chercher du bon côté.
Je suis pas sur que ce soit vraiment un exercice de débutant, ou alors c'est que j'ai encore beaucoup de chemin à faire (ce dont je ne doute pas).

Comme je l'ai dit, c'est un exercice qu'on peut poser à des "débutants" parce qu'il est aussi difficile quel que soit le niveau, à partir du moment où on sait manipuler (afficher et potentiellement modifier) des chaines de caractères.

Ceci dit, pas la peine de lui attacher une importance spécifique, dans le domaine de la programmation c'est une curiosité, rien de plus.

Si j'arrive à trouver un indice potable (qui met sur la voie, mais sans dévoiler la solution), je le posterai.

#include <stdio.h>

int main(void){
    char str[1000] = "#include <stdio.h>\n\nint main(void){\nchar str[1000] = \"";
    printf("%s%c%s%c;\n", str, '"', str, '"');
    return 0;
}

Un programme qui montre son code source me fait penser à une mise en abyme.

Pour le problème du cavalier j'me demande si c'est pas plus simple que ça.
On sait que c'est possible sur un échiquier 8*8 peut être que y'a un rapport logique à faire entre la largeur et la longueur de l'échiquier.

Si j'ai saisie ton code là il affiche (en omettant les \t)

#include <stdio.h>

int main(void){
char str[1000] = ""#include <stdio.h>

int main(void){
char str[1000] = ""

Comme l'impression que on doit aussi oublier les \n normalement.

21 > l'approche du problème n'est pas "on va trouver une condition sur les dimensions pour que ça marche". Si ça peut t'aider, la réponse est "oui" dès que les dimensions sont plus grosses que 3x3 (je ne l'ai pas démontré, je l'ai juste constaté empiriquement jusqu'à 500x500). Le but de la question est de trouver un chemin qui marche (sans forcément pouvoir le retrouver ensuite, c'est le but de la deuxième question et c'est un peu plus difficile) : il faut que ton algorithme soit passé par un chemin correct pour que ton répondes oui.

Bonjour,
suite à la remarque judicieuse de bluestorm sur mon code ci-dessous:

j'ai donc modifié mon code, ce qui me donne ceci :


Dans le premier cas à l'exécution il me donne un resultat au bout de 0.031s
Et le deuxième cas : 0.016s. Je pourrais m'en contenter et être satisfait puisque à priori ma deuxième version est plus rapide (je parcours la chaine une seule fois).Or justement pour y arriver j'emploie du coup un tableau pour comptabiliser mes occurences, donc j'emploie plus de mémoire !
Avez vous trouver une solution intermédiaire qui soit rapide (peut-être plus rapide que la mienne) et peux couteuse en ressource mémoire ?
@+

Sauf que :
- en dessous de 0.5s, ça ne vaut rien pour les mesures, l'imprécision est trop importante. Il faut que tu testes sur une grosse chaîne, par exemple :

#define LEN 10000
char str[LEN];
for (i = 0; i < LEN; ++i)
    str[i] = i % 255 + 1;
char str[LEN-1] = '\0';

- l'utilisation de mémoire supplémentaire est "négligeable" par rapport à ton gain de temps; si tu étais dans un environnement avec de fortes contraintes, ça vaudrait peut-être le coup de l'éviter, mais en l'état c'est ridicule

- si tu utilises une solution avec plus de mémoire, c'est que tu auras fait un sacrifice au niveau du temps, donc elle pourrait difficilement être plus rapide

- tu devrais enlever le code qui ne sert à rien et qui a tendance à fausser les mesures (printf("Exercice du moi de mars..."); affichage de la chaîne..)

- les commentaires de ton deuxième code sont complètement faux, tu devrais les enlever

A zx-spectrum > le problème de ton code est que si je me rappel bien le post d'Eusebus on doit ne considérer que les caractères... Je dirais même uniquement les minuscules ou les majuscules (au choix et tu fais une conversion : toupper() - tolower() ).

Citation : bluestorm

tu devrais enlever le code qui ne sert à rien et qui a tendance à fausser les mesures (printf("Exercice du moi de mars..."); affichage de la chaîne..)

Tu peux utiliser la macro puts(), ce qui évite un appel de fonction qui comme souligné peut fausser les mesures.

bonjour,

Citation : Campous

A zx-spectrum > le problème de ton code est que si je me rappel bien le post d'Eusebus on doit ne considérer que les caractères... Je dirais même uniquement les minuscules ou les majuscules (au choix et tu fais une conversion : toupper() - tolower() ).

C'est juste, mais j'ai fait volontairement cela : qui peut le plus, peut le moins !

Citation : bluestorm

- les commentaires de ton deuxième code sont complètement faux, tu devrais les enlever

Effectivement, je les ai enlevés

Merci pour vos remarques
@+

Bon, alors ton algo est exactement en O(2*256+n), donc si l'on simplifie, on a du O(n+256) et donc du O(n). C'est à peu près la même chose que bluestorm, sauf que tu passes par une variable i inutile. Comme bluestorm l'a dit, c'est négligeable ça, mais autant l'éviter quand c'est si flagrant.

Ainsi, (i= chaine[j]; compte[i]++;) devient (compte[chaine[j]]++;).

C'est quoi votre truc avec O(x) ?

21 > Complexité algorithmique, une petite recherche avec ces termes devrait t'aider.

bonjour

Citation : ShareMan

Bon, alors ton algo est exactement en O(2*256+n), donc si l'on simplifie, on a du O(n+256) et donc du O(n). C'est à peu près la même chose que bluestorm, sauf que tu passes par une variable i inutile. Comme bluestorm l'a dit, c'est négligeable ça, mais autant l'éviter quand c'est si flagrant.

Ainsi, (i= chaine[j]; compte[i]++;) devient (compte[chaine[j]]++;).

sauf que si ton compilo est bien reglé tu devrais avoir ceci :

||=== a, Debug ===|
C:\Documents and Settings\J Luc\Mes documents\sobetra\a\main.c||In function `main':|
C:\Documents and Settings\J Luc\Mes documents\sobetra\a\main.c|35|warning: array subscript has type `char'|
||=== Build finished: 0 errors, 1 warnings ===|

et donc c'est pour cela que j'utilise une variable temporaire i !
@+