I- Présentation du problème
A) Les entrées
En entrée on nous donne un entier.
B) Le but du jeu
Une rivière numérique est une séquence de nombres où chaque nombre est suivi du même nombre plus la somme de ses chiffres. Dans une telle séquence, 123 est suivi de 129 (puisque 1 + 2 + 3 = 6), qui est à son tour suivi de 141.
Nous appelons une rivière numérique rivière K, si elle commence par la valeur K.
Par exemple, la rivière 7 est la séquence commençant par {7, 14, 19, 29, 40, 44, 52, ... } et la rivière 471 est la séquence commençant par {471, 483, 498, 519, ... }.
Les rivières numériques peuvent se rencontrer. Cela se produit lorsque deux rivières numériques partagent les mêmes valeurs. La rivière 32 rencontre la rivière 47 à 47, tandis que la rivière 471 rencontre la rivière 480 à 519.
Étant donné un nombre, décidez s'il peut s'agir d'un point de rencontre de deux ou plusieurs rivières numériques. Par exemple, il est facile de vérifier que seule la rivière 20 contient le nombre 20 dans sa séquence (comme point de départ).
C) La sortie
On doit retourner si oui ou non le nombre de départ fait partie d'une rivière.
II- Ma méthode de résolution
A) Approche synoptique
Pour résoudre ce problème, j'ai utilisé la même méthode qu'au problème river 1. Des divisions entières et des restes de divisions. Je testais à chaque itération un nombre plus petit que le nombre en question. Ceci me permettait de déterminer si une rivière pouvait posséder le nombre en question dans sa suite.
B) Appproche algorithmique et explication de mon programme
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
int somme(int nb){
int somme=nb;
while (nb!=0){
somme+=nb%10;
nb=nb/10;
}
return somme;
}
int main(){
int r_1,nb_depart,somme_nb_preced;
scanf("%d", &r_1);
nb_depart=r_1;
somme_nb_preced=somme(r_1);
while (somme_nb_preced!=nb_depart && r_1>0){
r_1--;
somme_nb_preced=somme(r_1);
}
if (somme_nb_preced==nb_depart){
printf("YES\n");
}
else {
printf("NO\n");
}
return 0;
}
Ce programme se base sur la même fonction annexe somme ue j'ai présenté précédemment, je ne vais donc par expliquer de nouveau le principe car c'est le même.
Néanmoins le programme principal est différent, J'initialise cette fois 3 variables entières, "r_1" , "nb_depart" et "somme_nb_preced". Je demande d'abord la valeur de "r_1" que je sauvegarde dans la variable "nb_depart". La variable "somme_nb_preced" vaut quand à elle somme(r_1). On rentre ensuite dans la boucle while qui s'arrètera lorsque "somme_nb_preced" sera égale à "nb_depart" ou si "r_1" est égale à 0. Dans cette boucle je soustrait 1 à "r_1" à chaque itération et je calcule la somme de ce chiffre avec la fonction du dessus. Concernant la fonction somme je l'ai modifé en initialisant les variables en tant que int du fait que les nombres sont plus petits qu'à la question 1.
Si la boucle a été stoppé, je regarde si "nb_depart" vaut "somme_nb_preced", dans ce cas j'affiche YES sinon j'affiche NO signifiant que le nombre ne peut pas être obtenu dans des rivières différentes de la sienne.
III- Un autre programme
#define N 100000
int sum(int n) {
return n ? n%10+sum(n/10) : 0 ;
}
int sieve[N];
void sieveCompute(void) {
for (int i = 1 ; i < N ; i++) {
for (int j = i ; sieve[j] == 0 && j < N ; j += sum(j)) {
sieve[j] = i;
}
}
}
int main() {
int r1;
scanf("%d", &r1);
sieveCompute();
printf( sieve[r1] == r1 ? "NO": "YES");
}
Il utilise comme dans river 1 la fonction qui calcule le nombre suivant dans la rivière, il ajoute aussi une autre fonction qui permet de déterminer si un nombre peut être obtenu à partir d'une rivière sans compter la sienne. Sa fonction main va quand à elle demander le nombre puis afficher si oui ou non ce nombre peut être obtenu à partir d'une rivière.
IV- Bilan / Retour d'expérience
J'ai appris au travers du programme écrit par une autre personne que l'on pouvait utiliser les variables en dehors de la fonction si on initialiser la fonction en type void et surtout si on ne donne pas d'arguments appart void.