Deux nombres freres
Résolu/Fermé
yassine
-
Modifié le 26 oct. 2021 à 14:28
[Dal] Messages postés 6194 Date d'inscription mercredi 15 septembre 2004 Statut Contributeur Dernière intervention 11 octobre 2024 - 28 oct. 2021 à 16:23
[Dal] Messages postés 6194 Date d'inscription mercredi 15 septembre 2004 Statut Contributeur Dernière intervention 11 octobre 2024 - 28 oct. 2021 à 16:23
A voir également:
- Deux nombres freres
- Deux ecran pc - Guide
- Deux comptes whatsapp - Guide
- Itinéraire google map entre deux adresses - Guide
- Faire deux colonnes sur word - Guide
- Code binaire des nombres - Guide
2 réponses
baladur13
Messages postés
46951
Date d'inscription
mercredi 11 avril 2007
Statut
Modérateur
Dernière intervention
28 novembre 2024
13 462
26 oct. 2021 à 14:32
26 oct. 2021 à 14:32
Bonjour,
Nous ne ferons pas votre exercice à votre place.
Merci de décrire précisément votre problème et en postant le code déjà réalisé.
Cliquez ici pour des conseils d'écriture des messages et ici concernant les devoirs scolaires ou PFE.
Pour poster votre code, merci de penser à la coloration syntaxique.
Nous ne ferons pas votre exercice à votre place.
Merci de décrire précisément votre problème et en postant le code déjà réalisé.
Cliquez ici pour des conseils d'écriture des messages et ici concernant les devoirs scolaires ou PFE.
Pour poster votre code, merci de penser à la coloration syntaxique.
mamiemando
Messages postés
33390
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
28 novembre 2024
7 803
Modifié le 27 oct. 2021 à 16:44
Modifié le 27 oct. 2021 à 16:44
Bonjour,
Par défaut j'aurais répondu comme baladur13, mais comme l'exercice n'est pas si facile que ça, je pense qu'on peut au moins te donner un point de départ et ensuite tu nous montres ce que tu as fait, où tu en es et ce qui te bloque.
Vu que tu n'as pas le droit aux chaînes il va falloir uniquement travailler avec ces deux entiers et récupérer un par un les chiffres qui les composent.
L'approche naturelle (hors sujet !)
Ton exercice si tu représentes tes deux entiers dans une chaîne de caractère en O(N1+N2), en s'appuyant sur un tableau auxiliaire (ici
Au passage, dans des langages plus haut niveau (comme python) ça s'écrit encore plus facilement/naturellement :
Retour à ton exercice
Pas de chance, si tu réponds ça tu es hors sujet mwahahaha :D Eh oui, on utilise des tableaux et des chaînes.
Bref, tu vas devoir prendre un chemin détourné (et c'est là que tu vas commencer à nous montrer tes capacités de programmation :p).
En gros il faut récupérer chaque chiffre disons de
À chaque fois que tu extrais un chiffre (dans mon exemple, 3 puis 2 puis 1) il faut parcourir
Ce que je viens de décrire permet de vérifier que les chiffres de
Bonne chance
Par défaut j'aurais répondu comme baladur13, mais comme l'exercice n'est pas si facile que ça, je pense qu'on peut au moins te donner un point de départ et ensuite tu nous montres ce que tu as fait, où tu en es et ce qui te bloque.
Vu que tu n'as pas le droit aux chaînes il va falloir uniquement travailler avec ces deux entiers et récupérer un par un les chiffres qui les composent.
L'approche naturelle (hors sujet !)
Ton exercice si tu représentes tes deux entiers dans une chaîne de caractère en O(N1+N2), en s'appuyant sur un tableau auxiliaire (ici
tab) qui permet de garder trace des chiffres rencontrés dans N1 et N2 :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
bool are_brothers(int n1, int n2) {
unsigned i;
bool tab[10];
char *pc;
char buffer[100];
bool brothers = true;
memset(&tab[0], 0, sizeof(bool) * 10);
sprintf(buffer, "%d", n1);
for (pc = buffer; *pc; pc++) {
i = *pc - '0';
tab[i] = 1;
}
sprintf(buffer, "%d", n2);
for (pc = buffer; *pc; pc++) {
i = *pc - '0';
tab[i] = 0;
}
for (i = 0; i < 10; i++) {
if (tab[i] != 0) {
brothers = false;
break;
}
}
return brothers;
}
int main(){
int n1, n2;
printf("n1? ");
scanf("%d", &n1);
printf("n2? ");
scanf("%d", &n2);
if (are_brothers(n1, n2)) {
printf("%d et %d sont frères\n", n1, n2);
} else {
printf("%d et %d ne sont pas frères\n", n1, n2);
}
return 0;
}
Au passage, dans des langages plus haut niveau (comme python) ça s'écrit encore plus facilement/naturellement :
#/usr/bin/env python3
# -*- coding: utf-8 -*-
def are_brothers(n1, n2):
return set(str(n1)) == set(str(n2))
n1 = int(input("n1 ? "))
n2 = int(input("n2 ? "))
if are_brothers(n1, n2):
print(f"{n1} et {n2} sont frères")
else:
print(f"{n1} et {n2} ne sont pas frères")
Retour à ton exercice
Pas de chance, si tu réponds ça tu es hors sujet mwahahaha :D Eh oui, on utilise des tableaux et des chaînes.
Bref, tu vas devoir prendre un chemin détourné (et c'est là que tu vas commencer à nous montrer tes capacités de programmation :p).
En gros il faut récupérer chaque chiffre disons de
n1, en faisant des divisions euclidiennes pour chaque puissance de 10 (par exemple
123 == 1 * 100 + 2 * 10 + 3 * 1). Je te conseille de commencer par les unités, puis les dizaines, les centaines etc, et t'arrêter jusqu'à avoir décomposé complètement le nombre. Pour cela il va falloir utiliser une variable auxiliaire qui permet de savoir où on en est. Par exemple, si tu as extrait les unités et les dizaines, tu as consommé
23 != 123, donc il faut continuer. Pour rappel, en C la division euclidienne se fait avec l'opérateur
/et le reste se récupère avec
%(par exemple
13 / 3 == 4et
13 % 3 == 1car
13 == 3 * 4 + 1).
À chaque fois que tu extrais un chiffre (dans mon exemple, 3 puis 2 puis 1) il faut parcourir
n2selon le même principe et voir si on le retrouve.
Ce que je viens de décrire permet de vérifier que les chiffres de
n1sont inclus dans
n2, mais il faut également faire le test dans l'autre sens pour s'assurer que
n1et
n2sont frères.
Bonne chance
[Dal]
Messages postés
6194
Date d'inscription
mercredi 15 septembre 2004
Statut
Contributeur
Dernière intervention
11 octobre 2024
1 092
Modifié le 27 oct. 2021 à 17:26
Modifié le 27 oct. 2021 à 17:26
Salut mamiemando,
Il faudrait aussi composer avec la restriction mentionnée par yassine "sans les tbaleaux,les chaines ou les listes", en particulier le sans "tableaux" et comprendre ce que cette interdiction signifie.
Par exemple, est-ce que cela veut dire, qu'on pourrait stocker les données de travail dans un espace mémoire alloué avec malloc, mais qu'on s'interdirait d'y accéder en utilisant l'opérateur
Il faudrait aussi composer avec la restriction mentionnée par yassine "sans les tbaleaux,les chaines ou les listes", en particulier le sans "tableaux" et comprendre ce que cette interdiction signifie.
Par exemple, est-ce que cela veut dire, qu'on pourrait stocker les données de travail dans un espace mémoire alloué avec malloc, mais qu'on s'interdirait d'y accéder en utilisant l'opérateur
[]et qu'on ne pourrait y accéder qu'avec l'arithmétique des pointeurs ?
[Dal]
Messages postés
6194
Date d'inscription
mercredi 15 septembre 2004
Statut
Contributeur
Dernière intervention
11 octobre 2024
1 092
>
[Dal]
Messages postés
6194
Date d'inscription
mercredi 15 septembre 2004
Statut
Contributeur
Dernière intervention
11 octobre 2024
27 oct. 2021 à 17:53
27 oct. 2021 à 17:53
Je pense aussi que, dans ton code, on peut remplacer :
par :
puisque le tableau n'a pas à être réinitialisé dans la fonction.
S'il s'avère que, dans son exercice, il ne peut pas utiliser de type tableau, mais juste des pointeurs et l’arithmétique de pointeurs, alors pour initialiser la mémoire allouée à 0, il pourra toujours utiliser calloc() qui fera les deux : allocation et initialisation à zéro.
https://www.cplusplus.com/reference/cstdlib/calloc/
bool tab[10]; memset(&tab[0], 0, sizeof(bool) * 10);
par :
bool tab[10] = { 0 };
puisque le tableau n'a pas à être réinitialisé dans la fonction.
S'il s'avère que, dans son exercice, il ne peut pas utiliser de type tableau, mais juste des pointeurs et l’arithmétique de pointeurs, alors pour initialiser la mémoire allouée à 0, il pourra toujours utiliser calloc() qui fera les deux : allocation et initialisation à zéro.
https://www.cplusplus.com/reference/cstdlib/calloc/
mamiemando
Messages postés
33390
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
28 novembre 2024
7 803
>
[Dal]
Messages postés
6194
Date d'inscription
mercredi 15 septembre 2004
Statut
Contributeur
Dernière intervention
11 octobre 2024
28 oct. 2021 à 14:00
28 oct. 2021 à 14:00
Bonjour [Dal],
Merci pour ton retour.
Par rapport à tes remarqies :
De toute façon, je n'ai pas l'impression qu'il faille dépenser plus de temps sur cette question en attendant que yassine se manifeste.
Bonne journée
Merci pour ton retour.
Par rapport à tes remarqies :
- Toute la première partie est clairement hors sujet (et marquée comme telle :p). Elle est uniquement là pour montrer comment on aurait résolu cet exercice avec une complexité minimale (ce qui en soit a un intérêt pédagogique, même si ça n'est pas celui de cet exercice). C'est également pour ça que j'ai donné un code prêt à cuire : il est hors sujet, et ce cher yassine aura quand même du pain sur la planche.
- Par rapport à l'initialisation dont tu parles, je ne connais pas cette syntaxe. J'aurais plutôt dit qu'il faut plutôt écrire
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}. Mais comme elle est contraire aux consignes ça n'est pas très important. - La seconde partie de mon message (voir "retour à ton exercice") propose de prendre un chemin radicalement différent, sans tableau / chaîne / liste. En soi, c'est intéressant de montrer au cours d'un exercice qu'on n'a pas tout le temps besoin de recourir à des concepts "évolués" pour répondre à un problème. Cependant ici, c'est mal fait, car cela se fait au détriment de la complexité algorithmique (car on va passer d'un algorithme en temps linéaire à un algorithme en temps quadratique), sans parler du code extrêmement laborieux que ça va engendrer. En ce sens, l'exercice n'est pas très bien pensé et un peu sadique.
De toute façon, je n'ai pas l'impression qu'il faille dépenser plus de temps sur cette question en attendant que yassine se manifeste.
Bonne journée
[Dal]
Messages postés
6194
Date d'inscription
mercredi 15 septembre 2004
Statut
Contributeur
Dernière intervention
11 octobre 2024
1 092
>
mamiemando
Messages postés
33390
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
28 novembre 2024
28 oct. 2021 à 16:23
28 oct. 2021 à 16:23
Salut mamiemando,
Oui, j'ai compris ton approche, et désolé si ma remarque sur ton initialisation du tableau n'a pas vocation à être utile dans cet exercice, l'usage de tableaux semblant effectivement interdit. Je voulais juste signaler un moyen plus pratique de faire ce que tu écris.
La syntaxe
Dans le standard C99 cela se trouve à 6.7.8 Initialization, § 21, mais cela existe dès C89 :-)
21 If there are fewer initializers in a brace-enclosed list than there are elements or members
of an aggregate, or fewer characters in a string literal used to initialize an array of known
size than there are elements in the array, the remainder of the aggregate shall be
initialized implicitly the same as objects that have static storage duration.
En clair, si le nombre d'éléments fournis pour l'initialisation est inférieur aux éléments que peut contenir l'agrégat (ici un tableau) le reste des éléments est implicitement initialisé de la même façon que les variables statiques (c'est à dire à 0).
C'est bien pratique au quotidien et on peut se passer de memset(), qu'on pourra utiliser en plus si la fonction doit remettre à 0 le contenu au cours de son exécution.
Sur le sujet et son interprétation...
Avec tes explications additionnelles, je comprends que ton interprétation de la restriction est que les valeurs récupérées ne peuvent pas non plus être stockées temporairement dans un espace mémoire alloué avec malloc (et accédées sans utiliser l'opérateur [] avec l'arithmétique de pointeurs comme je l'évoquais), et que le seul stockage temporaire serait celui du chiffre courant récupéré dans une variable simple (un
Bonne journée à toi aussi !
P.S. : ne te sens pas obligée de réponse à ce post, je pense, comme toi qu'il faut que yassine s'exprime maintenant :-)
Oui, j'ai compris ton approche, et désolé si ma remarque sur ton initialisation du tableau n'a pas vocation à être utile dans cet exercice, l'usage de tableaux semblant effectivement interdit. Je voulais juste signaler un moyen plus pratique de faire ce que tu écris.
La syntaxe
bool tab[10] = { 0 }; au lieu de bool tab[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; est équivalente selon le standard du C.
Dans le standard C99 cela se trouve à 6.7.8 Initialization, § 21, mais cela existe dès C89 :-)
21 If there are fewer initializers in a brace-enclosed list than there are elements or members
of an aggregate, or fewer characters in a string literal used to initialize an array of known
size than there are elements in the array, the remainder of the aggregate shall be
initialized implicitly the same as objects that have static storage duration.
En clair, si le nombre d'éléments fournis pour l'initialisation est inférieur aux éléments que peut contenir l'agrégat (ici un tableau) le reste des éléments est implicitement initialisé de la même façon que les variables statiques (c'est à dire à 0).
C'est bien pratique au quotidien et on peut se passer de memset(), qu'on pourra utiliser en plus si la fonction doit remettre à 0 le contenu au cours de son exécution.
Sur le sujet et son interprétation...
Avec tes explications additionnelles, je comprends que ton interprétation de la restriction est que les valeurs récupérées ne peuvent pas non plus être stockées temporairement dans un espace mémoire alloué avec malloc (et accédées sans utiliser l'opérateur [] avec l'arithmétique de pointeurs comme je l'évoquais), et que le seul stockage temporaire serait celui du chiffre courant récupéré dans une variable simple (un
intici). Si c'est effectivement le cas, l'exercice est très tordu. Peut-être que yassine devrait vérifier cela auprès de son enseignant, car s'il peut décomposer des chiffres (comme tu le proposes par division euclidienne) et stocker les chiffres récupérés en mémoire pour les traiter une fois qu'il les a récupérés tous, cela change pas mal de choses...
Bonne journée à toi aussi !
P.S. : ne te sens pas obligée de réponse à ce post, je pense, comme toi qu'il faut que yassine s'exprime maintenant :-)