SOS besoin d'aide programmation

Question

Bonjour a tous voila j'ai un probleme de programmation mais je ne sais pas comment faire je suis neophite en la matiere voila mon probleme . comment programmer ceci en C . dans un fichier j'ai des entiers ( 10 par ligne ) ex 1 2 3 4 5 6 7 8 9 10 1 2 5 7 9 10 11 13 14 15 ..... ..... ..... dans mon programme je genere toutes les combinaisons possibles de 1 a 25 de 10 chiffres C ( 10 25 ) ce qui fait 3 268 760 combinaisons chaque combinaisons generé doit etre verifier avec chaque ligne de mon fichier ( donc verifier chffre par chiffre) quand un chiffre est commun je doit incrementer un compteur ,faire cela jusqu'a la fin des combinaisons generées . comment programmer ce genre de choses de façon a ce qu'il soit le plus optimiser possible ? ( par exemple les boucles imbriquées qui sont tres nombreuse , recursivité ... enfin bref je sais pas ;-) ) merci de votre aide cordialement ps) pardon pour les fautes

THEwarrior333 · Answer

Salut
je n'ai pas bien compris le principe de ton programme mais un conseil: evite la recursivite qui est souvent bien moins performante que la methode iterative meme si elle est plus jolie a voir.
Ensuite qq techniques permettent d'optimiser le traitement des boucles. Par exemple, for(int i=0; i<MAX; ++i) est legerement plus rapide que for(int i=0; i<MAX; i++) . Ensuite, si tu imbriques deux boucles pour un parcours de tableau, fais en sorte que la boucle imbriquée parcours sur les lignes du tableau car l'accès en mémoire sera plus rapide.

yann_lo_san · Answer

Heu, sans affirmer quoi que ce soit, ton ++i demarre la boucle à 1 et fait passer à l'as le test sur [0], de plus le code assembleur généré ne me parait pas plus rapide, mais j'ai peut être mal compris...

ria94 · Answer

Tu charges ton fichier dans un tableau de int 10 par 10  et tu compares chaque ligne de ton tableau avec tes 3 268 760 combinaisons

Je part du principe que tu fais une boucle qui englobe ce bou de code afin de remplir ton tableau de combinaison.
Voila comment j'aurai fait mais je t'avoue que j'ai peut etre mal compris ce que tu voulais parce que je ne comprend pas vraiment l'utilité.
int compteur = 0;
int tab_fichier[10][10];
int tab_combinaison[10];
int i,j;

 for(i=0; i<10; i++)
{
    for(j=0; j1<10; j1++)
   {
        tab_fichier[i][j]  = tab_combinaison[j];
         compteur++;
    }
 }

luhtor · Answer

si for (... ++i) commence bien à 0 et est (il parait) plus rapide que for (...i++)
Pour
les algo récursive, si le niveau de récursivité est faible, moi je
voyais pas de différence en temps d'éxécution sur mes progs.

mad_love_disease · Answer

En effet yann_lo_san,


la ou tu a raison thewarrior333 c'est qu'une méthode récursive
n'est pas tres envisageable vu le nombre de calcul à effectuer ainsi
que la simplicité du problème; Bref, si j'ai bien compris tu dois
Vérifier le fichier texte contenant le nombre et non le générer. Pour
ça, je crois que le meilleur moyen est de parcourir tout le fichier
texte en comptant l'occurence de chaque nombre, par colone et par ligne.  Un petit
test d'égalité à la fin pour les compteurs en colone et un petit test pour chaque combinaisons de nombre en ligne et c'est bon. Je m'explique:

Prenons ton exemple, un fichier généré avec C ( 3 2) nos chiffres seront 0 et 1. ( et oui, on en sort jamais)

on obtient:

    000    compteur 0=3  ; compteur 1=0
    100    compteur 0=2  ; compteur1=1
    010    ........
    001
    011
    101
    110
    111

Pour chaque colone on compte 4 zéros et 4 un.
Pour les lignes on a:
1fois 3 zéros et 1 fois 3 un.  C (3 1) = 1possibilité
3fois 2 zéros et 2 un               C(2  2) + je ne sais koi
3fois 1 zéro et 1 un                C(1 3)   sans répétitions

Bref, je ne suis pas très douer en maths mais l'intuition me dit que la somme des compteurs égaux pour chaque nombre ( en ligne) sont eux aussi égaux. 

ca fait pour ton cas 10*25*25 compteurs... (6250)
Ca te fait beaucoup de compteur c'est vrai, mais surement moins que mémorisé les 3 268 760 combinaisons.

Si tu ne compte pas les chiffres en lignes et tu ne compte qu'en colone, les résultats trouvés peuvent être faux, exemple:

pour C(2 2) avec 1 et 0

11 
00
00
11

En esperant être clair....

 Mad_Love_Disease

mad_love_disease · Answer

et on compte aussi zéro fois zéros et zéro fois un


j'avais oublié celui la... @pluche

 Mad_Love_Disease

zhao77 · Answer

bBonjour a tous et merci de vos reponses ,precision : pour la generation des combi voila comment je procede si vous avez un algo plus rapide je suis preneur ;-) #include #include #include main() { int tc[10]; int nt=0; register int i,j,k,l,m,n,o,p,q,r; FILE *fichier; fichier=fopen("test.txt","r"); printf("entrez votre valeur "); scanf("%d",&nt); a=nt-9; for(i=1;i<=a;i++) for(j=i+1;j<=a+1;j++) for(k=j+1;k<=a+2;k++) for(l=k+1;l<=a+3;l++) for(m=l+1;m<=a+4;m++) for(n=m+1;n<=a+5;n++) for(o=n+1;o<=a+6;o++) for(p=o+1;p<=a+7;p++) for(q=p+1;q<=a+8;q++) for(r=q+1;r<=a+9;r++) tc[0]=i;tc[1]=j;tc[2]=k;tc[3]=l;tc[4]=m;tc[5]=n, tc[6]=o;tc[7]=p;tc[8]=q;tc[9]=r; } ensuite quel est la syntaxe pour que chaque chiffre de la combinaison generer soit comparer avec chaque chiffre de chaque ligne de mon fichier ? par exemple admettons que la combi generer soit celle ci : 1 2 3 4 5 6 7 8 9 10 et que dans mon fichier j'ai ceci : 2 3 7 8 9 11 12 15 17 20 7 8 11 16 18 19 21 22 23 25 ......... ......... ......... etc.... je doit comparer tous les chiffres de ma combi generer avec tous les chiffres de la premier ligne et ceux de la deuxieme ligne etc...et ceci jusqu'a la fin de mon fichier et recommencer cette operation jusqu'as la derniere combinaisons generer ,cela represent un sacré paquets de tests donc l'optimisation est la bien venu ;-)) cordialement

mad_love_disease · Answer

Je ne comprends pas très bien si tes combinaisons sont ordonnées ou non, avec ou sans répétitions

Peut on avoir 1 1 1 1 1 1 1 1 1 1 
ou encore       25 1 2 3 4 5 6 7 8 9 (et) 1 2 3 4 5 25 6 7 8 9

Mad_Love_Disease

mad_love_disease · Answer

Ok, je crois que j'ai trouvé une solution.

Ce que j'ai dit auparavant était valable pour les combinaisons "avec répétitions", ici on a faire (vu ton algo de génération ainsi que le nombre de combis possible) aux combinaisons sans répétions non ordonnés. Pour savoir si ton fichier est valide, il te faut vérifier trois choses;

- La première et ca va de soi est de vérifier si le nombre de combinaisons dans le fichier est égale aux nombre de combinaisons attendue

- La deuxième est de vérifier que les combinaisons sont valides (pas de chiffres invalide (>25 ou <1) et pas de répétitions)

- La troisième est de compter le nombre de combinaisons contenant chaque chiffre. En effet, il y aura autant de combinaisons contenant un 1 que de solutions contenant un 2, un 3 ou un 25 (dans ton cas). 

un exemple avec C(4 5)

on a :

1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5

on compte 5 combinaisons (résultat attendu)
il n'y a pas de combinaisons invalides
il y a:  

- 4 combinaisons comprenant un 1
- 4 combinaisons comprenant un 2
- 4 combinaisons comprenant un 3
- 4 combinaisons comprenant un 4
- 4 combinaisons comprenant un 5

le fichier est bon...

 Mad_Love_Disease

mad_love_disease · Answer

Si ca t'interesse je viens de le coder, ca pourrait te servir à vérifier ton programme, j'ai utilisé ton algo pour la génération et l'idée du dessus pour la résolution et ca marche. Bon courage pour le code!!

 Mad_Love_Disease

zhao77 · Answer

Bonjour 

oui cela m'interesse surtout la partie pour lire le fichier et les tests ;-)
ensuite dans le fichier il n'est pas necessaire que le nombre de combi le composant soit egal au nombre de combi que je souhaite generer , si par exemple je genere toute les combi de C( 10 - 25 ) ce qui fait plus de 3 millions de combi a generer je peut tres bien avoir dans le fichier que 10 ,1000 ,1758 etc .. combinaisons enregistrer cela n'est pas un probleme ;-)
cordialement

mad_love_disease · Answer

ok Zhao,


Le seul petit problème c'est que la méthode précédemment énoncée sera fausse si toutes les combinaisons ne sont pas présentes

s'il manque des combinaisons: le fichier généré fera 82 mo pour C(10 25). Une petite question, peut on avoir deux fois la même combinaison dans le fichier?

Je t'envoie ça dès que j'ai du temps.

 Mad_Love_Disease

zhao77 · Answer

Bonjour ,

Mad_Love_Disease ,en principe non mais cela n'as pas d'importance car le but  est celui ci :

prenon par exemple mon fichier admettons qu'il contienne 5 lignes les données suivantes:

A) 1 2 3 4 5 6 7 8 9 10     
B) 1 2 5 7 9 10 13 15 17 19
C) 1 2 5 6 7 8  9 19 21 22
D) 1 2 5 7 10 18 19 22 23 25
E) 1 2 5 7 9 11 13 14 15 16
 et que la combinaisons en cours soit celle la :

1 2 3 4 5 6 7 8 9 10

si je fais les tests je souhaiterais avoir  comme resultat afficher a la fin du programme "c'est a dire une fois que toutes les combinaisons generer aurons été testé  et supposons pour faire plus simple qu'il n'y est qu'une seule combi " 
ceci:

nombre de combi ayant 
10  CHIFFRES EN COMMUN  :  1 ( LIGNE A )
  9  CHIFFRES EN COMMUN  :  0
  8  CHIFFRES EN COMMUN  :  0
  7  CHIFFRES EN COMMUN  :  1 ( LIGNE C )
  6  CHIFFRES EN COMMUN  :  1 ( LIGNE B )
  5  CHIFFRES EN COMMUN  :  2 ( LIGNE D ET E )
  
merci beaucoup pour ton aide :-)
cordialement

mad_love_disease · Answer

ok zhao, mais ta méthode reste basée sur le principe de comparaison entre toutes les combinaisons, ce qui est extremement couteux. Si tu désires t'engager dans cette voie il faut prendre plusieurs choses en considération:

tout d'abord, ta première ligne aurait pu être: 1 2 3 4 5 6 7 8 10 9 et elle aurait aussi eu 10 chiffres en commun avec 1 2 3 4 5 6 7 8 9 10. Je te conseille donc de trier tes combinaisons par ordre croissant pour pouvoir comparer les nombres colonnes par colone. Ce qui fera 10 tests au total au lieu de 9+8+7+...+2+1, 45 tests pour une double boucle imbriquée. 4 fois plus rapide. Si tu veux, on peut même faire encore plus rapide en réduisant le test à un si tu donne aux combinaisons un "identifiant unique" permettant de savoir les chiffres que chaque combinaisons comportent en commun, j'ai une idée la dessus si ca t'interesse. Bon courage,

 Mad_Love_Disease

zhao77 · Answer

Bonjour 
escuse j'ai oublier de te preciser que les lignes dans le fichier sont deja trier par ordre croissant ( ou alors j'ai pas compris ce que tu voulais dire ) 
je m'explique :
tu ne peut pas avoir dans le fichier ce genre de chose :

A)  2 3 4 5 6 7 8 9 10 11
B) 1 2 3 4 5 6 7 8 9 10

B seras obligatoirement avant A et non l'inverse 
ensuite chaque chiffre par ligne est superieur a son precedent exemple  pour B) 2 > 1   3>2 etc.. tu ne peut avoir un chiffre intercaler dans une ligne qui soit inferieur exemple dans le fichier je ne peut pas avoir ceci :

1 2 4 "3" 5 6 7 8 9 10

mais au cas ou j'aurais mal compris et que tu as le moyen de reduire par 4 le nombre de test oulalalalalla je suis PRENEURRRRRRRRRRRRRRR  car le nombre de test est quand meme tres important surtout si le fichier contient plusieurs millions d'enregistrement    ;-)
en tout cas merci de t'interesser a mon probleme  ;-)
bien cordialement

mad_love_disease · Answer

Ok, Le fait que les nombres soient trier par odre croissant te permet d'éviter l'algo type double boucle pour vérifier l'égalitée de deux listes de chiffres: for(int n=0 ; n<10 ; n++) for(int i=0; i<10 ; i++) ---- Bref, tu as juste: for(int n=0 ; n<10 ; n++) .... Ce que je te propose pour réduire tes tests, c'est de donner un identifiant "unique pour chaque combinaison", ainsi, tu fera seulement un test a chaque fois : identifiantcombinaison1 == identifiantcombinaison2 ? Tu parcours d'abord le fichier une fois et tu créé l'identifiant unique pour chaque combinaisons, ensuite tu execute l'algo que tu avais prévu mais tu teste avec les identifiants que tu as crée. Puisque qu'ils sont uniques, si un test se révèle vrai cela voudra dire que deux combinaisons sont identiques dans le fichier. Mais comment créer cet identifiant unique va tu me dire?? pour cela, on utilisera un unsigned int qui fait 4octet soit 32 bit. on aura donc 00000000 00000000 0000000 00000000 : ceci est le code binaire du nombre 0 en unsigned int puisque que tu as 25 chiffre possible, 25 bit suffise à identifier une des combinaisons du fichier le dernier bit sera à 1 si ta combinaison comporte un 1 l'avant dernier sera à 1 si ta combi comporte un 2 ... ... ... enfin le 8ème dans l'ordre sera à 1 si la combi comporte un 25 on aura donc: 1 2 3 4 5 6 7 8 9 10 -> premiere combi -> code binaire= 00000000 0000000 00000011 11111111= 2047 en base 10 1 2 3 4 5 6 7 8 9 11 -> deuxième combi ->code binaire= 00000000 0000000 00000101 11111111= 3072 en base 10 ..... etc 16 17 18 19 20 21 22 23 24 25 -> 00000001 11111111 10000000 00000000 -> beucoup en base 10 Toutes tes combis auront un unsigned int les qualifiant. Aisni, pour tester l'égalité entre deux combis, cela reviendra à tester l'égalité entre deux unsigned int!!! Vali, Mad_Love_Disease

zhao77 · Answer

Bonjour Mad_Love_Disease,

je vais attendre de voir ton source pour mieux comprendre car la c'est pas evident n'oublie pas que je suis un neophyte ;-)

donc je suis tres impatient de voir ton programme ;-)

bien cordialement

mad_love_disease · Answer

ok, voila un exemple pour faire un id à partir de combinaisons 10 parmis 25, bon ya des variables globales c pas terrible mais ca marche (jsuis au boulot koi...). je vais mettre mes anciens prog (ceux qui marchent si toutes les combinaisons sont dans le fichier avec ton générateur) sur ftp et je te filerai l'adresse. avec ce prog tu rentre une combi à la main et la fonction te donne l'id unique: #include using namespace std; unsigned int masque[25]; //pas beau, tu me fera une classe fonction pour tout ca!! unsigned int gen_id(unsigned int combi[10]) { unsigned int res(0); //res=0 soit 00000000 00000000 00000000 00000000 bool temp(true); unsigned int chiffre,rang,cpt(0); for(chiffre=1 ; (chiffre<26) && (cpt<10) ; chiffre++) { temp=true; for(rang=0 ; (rang<10) && (temp==true) ; rang++) if(combi[rang] == chiffre) /*si le chiffre fait partit de la combi on met a 1 le bit correspondant a ce chiffre avec un ou logique*/ { res=res|masque[chiffre-1]; temp=false; cpt++; } } return res; } int main() { unsigned int chiffre,rang,combi[10]; //on initialise les masques d abord ...00001 puis ...000010 ...etc //on le fait la pour eviter de le faire X fois dans la fonction au dessus ( et c pour ca que c est en global) chiffre=1; for(rang=0 ; rang<25 ; rang++) { masque[rang]=chiffre; chiffre*=2; } //test pour une combi for(rang=0 ; (rang<10) ; rang++) cin>>combi[rang]; //et voila le resultat cout<<"id: "<

nightlord666 · Answer

Pour optimiser, je pense que c'est quand même beaucoup plus rapide de faire un ++i qu'un i++ :

i++ : Sauvegarde de i dans la pile
         Incrémentation de i

++i : incrémentation de i

Bon c'est pas grand chose, mais pour une fonction qui doit être appellée très souvent, ça peut diminuer de beaucoup le temps de calcul.

<hr size="2" width="100%" />Sachant qu'on peut toujours enlever une ligne à un programme, et que dans un programme il y a toujours un bug, un programme peut se résumer à une ligne avec un bug.

zhao77 · Answer

Bonjour Mad_Love_Disease ;-)

tout d'abord merci de ton aide ,cela change des personnes qui donnent des conseils et qui disent faut faire ca ou cela ,mais sans le moindre bout de code au moins avec toi c'est du concret ;-)
peut tu me transformer ce code en C classique car je ne comprends rien n'oublie pas que je suis totalement neophyte ,donc le C++ connais pas et les histoires de bits etc... encore bien moins ,je vais donc attendre la fin de ton programme pour "essayer de comprendre " car la je vois pas tres bien en quoi c'est plus rapide ,j'ai lancer ton programme et il me donne en retour un ID mais cela corresponds a quoi cet ID pour mon probleme ? tu vois j'ai rien compris ;-(
en tout cas merci :-)
cordialement

mad_love_disease · Answer

Yop, je suis content de pouvoir t'aider. En fait cet id identifie la combinaison. Comme cela, au lieu de tester tout les chiffres de tes combinaisons un à un (vu qu'il y en 10, ca fait 9 + 8 + 7 +...+2 +1 tests pour savoir si deux combinaisons sont identiques, tu me suis? Cet identifiant, calculer au début du programme te permettra à l'avenir de faire qu'un seul test a chaque fois identifiant de la combinaison 1 == identifiant de la combinaison 2. Vu que ces tests vont etre fait souvent apres. Vu que tu test toutes tes combis entre elle. Il est la le gain. Je retourne au boulot, je te remet un mesage dans la journée;

@pluche.

Mad_Love_Disease

zhao77 · Answer

ah ok je comprends mieux ,mais attention je ne cherche pas a savoir si une COMBINAISON est egal a une autre MAIS simplement combien de chiffre il y a en commun et chaque fois qu'un chiffre de la combinaison est egal a un chiffre de la combinaison  du fichier un compteur les comptabilise , donc en theorie le fichier doit etre parcouru a chaque fois en entier a moins qu'il y a une astuce pour l'eviter mais je vois pas comment , donc a moins que j'ai mal compris ce que tu voulais dire ce n'est pas LA COMBINAISON que je teste MAIS chaque chiffre de la combinaison generer avec chaque chiffre de toutes les combinaison contenu dans le ficheir ;-)
@+ ;-)

mad_love_disease · Answer

Ok,

Dans ce cas ce que j'ai fait est inutile , je suis désolé de t'avoir entrainer dans une mauvaise piste, peut tu me rapeller l' objectif réel de ton programme. Tu ne voulais pas savoir si tes combinaisons n'exite pas en double dans le fichier? J'ai du mal à comprendre, sorry....

Mad_Love_Disease

zhao77 · Answer

Bonjour Mad_Love_Disease 

Ne soit pas desolé car c'est de ma faute , donc je vais preciser mon objectif .

que la combinaison soit en double cela n'as aucune importance car ce qui m'interesse c'est le nombre de chiffre en commun entre la combinaison que je genere et les combinaisons se trouvant dans le fichier ;-)
prenon un exemple :

supposons que la combinaison generer ( avec l'algo que j'ai posté )soit :
A)  1 2 3 4 5 6 9 10 11 12 

et que dans mon fichier j'ai par exemple 2 combinaisons :
X)  1 2 3 7 8 10 11 14 17 18
Z)   4 6 7 9 10 12 16 17 21 23

si je fais mes tests de comparaisons je trouve que 
A possede  5 chiffres en commun avec X ( 1 2 3 10 et 11)
A possede  3 chiffres en commun avec Z ( 7 10 et 17 )

donc mon compteur sera de 5 car c'est la plus grande valeur que je conserve 
et je refais cette operation pour la combinaisons generer suivante jusqu'a la fin des combinaisons generer .
voila c'est tout ;-)
cordialement
@+ ;-)

SOS besoin d'aide programmation

24 réponses

Votre réponse

Discussions similaires