zhao77
Messages postés26Date d'inscriptionvendredi 8 septembre 2006StatutMembreDernière intervention 7 août 2008
-
3 oct. 2006 à 11:52
zhao77
Messages postés26Date d'inscriptionvendredi 8 septembre 2006StatutMembreDernière intervention 7 août 2008
-
11 oct. 2006 à 01:53
<hr style="color: rgb(209, 209, 225);" size="1" />
<!-- / icon and title -->
<!-- message -->
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 ;-) )
THEwarrior333
Messages postés192Date d'inscriptionvendredi 19 mars 2004StatutMembreDernière intervention30 janvier 2008 3 oct. 2006 à 14:18
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
Messages postés1137Date d'inscriptionlundi 17 novembre 2003StatutMembreDernière intervention23 janvier 201626 3 oct. 2006 à 16:25
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
Messages postés97Date d'inscriptionmercredi 28 mai 2003StatutMembreDernière intervention 3 octobre 2006 3 oct. 2006 à 17:16
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;
luhtor
Messages postés2023Date d'inscriptionmardi 24 septembre 2002StatutMembreDernière intervention28 juillet 20086 3 oct. 2006 à 17:29
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.
Vous n’avez pas trouvé la réponse que vous recherchez ?
mad_love_disease
Messages postés64Date d'inscriptionlundi 20 octobre 2003StatutMembreDernière intervention 1 juillet 20103 3 oct. 2006 à 17:32
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)
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:
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
Messages postés64Date d'inscriptionlundi 20 octobre 2003StatutMembreDernière intervention 1 juillet 20103 4 oct. 2006 à 14:11
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
mad_love_disease
Messages postés64Date d'inscriptionlundi 20 octobre 2003StatutMembreDernière intervention 1 juillet 20103 4 oct. 2006 à 14:35
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!!
zhao77
Messages postés26Date d'inscriptionvendredi 8 septembre 2006StatutMembreDernière intervention 7 août 2008 5 oct. 2006 à 00:51
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
Messages postés64Date d'inscriptionlundi 20 octobre 2003StatutMembreDernière intervention 1 juillet 20103 5 oct. 2006 à 08:51
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?
zhao77
Messages postés26Date d'inscriptionvendredi 8 septembre 2006StatutMembreDernière intervention 7 août 2008 5 oct. 2006 à 10:02
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 )
mad_love_disease
Messages postés64Date d'inscriptionlundi 20 octobre 2003StatutMembreDernière intervention 1 juillet 20103 6 oct. 2006 à 11:58
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,
zhao77
Messages postés26Date d'inscriptionvendredi 8 septembre 2006StatutMembreDernière intervention 7 août 2008 6 oct. 2006 à 12:41
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
Messages postés64Date d'inscriptionlundi 20 octobre 2003StatutMembreDernière intervention 1 juillet 20103 6 oct. 2006 à 14:38
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:
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 :
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!!!
mad_love_disease
Messages postés64Date d'inscriptionlundi 20 octobre 2003StatutMembreDernière intervention 1 juillet 20103 9 oct. 2006 à 17:02
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: "<<gen_id(combi)<<endl;
nightlord666
Messages postés746Date d'inscriptionvendredi 17 juin 2005StatutMembreDernière intervention23 mai 200710 9 oct. 2006 à 17:21
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
Messages postés26Date d'inscriptionvendredi 8 septembre 2006StatutMembreDernière intervention 7 août 2008 10 oct. 2006 à 02:01
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