Accélerer l'éxécution [Résolu]

SMM@ 12 Messages postés dimanche 7 février 2016Date d'inscription 18 mai 2017 Dernière intervention - 16 mars 2017 à 01:20 - Dernière réponse :  SMM@
- 16 mars 2017 à 21:25
bonjour
j'ai essayé de faire ce petit programme
while(n>0){
n=n-jour;
if(n>0) {n=n+m;jour++;}
if(n>nini) n=nini;


}

et je veux qu'il s'éxécute en 1s maximum le n et le m sont entrez par l'utilisateur et elle peut prend de 1 jusqu'à 10^18 le probléme quand le n et le m grand le programme prend beaucoup de temp pour s'éxécuter j'ai essayé d'utiliser les thread mais ca change rien si il ya une solution merci d'avance
Afficher la suite 

4 réponses

Répondre au sujet
KX 15101 Messages postés samedi 31 mai 2008Date d'inscriptionModérateurStatut 18 décembre 2017 Dernière intervention - 16 mars 2017 à 07:07
0
Utile
3
Bonjour,

À quoi sert ton programme ?

"le n et le m sont entrez par l'utilisateur"
jour et nini correspondent à quoi ?

Tu as des exemples d'exécution ?
SMM@ 12 Messages postés dimanche 7 février 2016Date d'inscription 18 mai 2017 Dernière intervention - 16 mars 2017 à 19:38
mon programme est un solution pour ce problème
http://codeforces.com/problemset/problem/785/C

voici le programme complet

import java.util.Scanner;

public class C785 {

public C785() {
Scanner in=new Scanner(System.in);
Long n,m,nini;

Long jour=1L;
n=in.nextLong();
m=in.nextLong();
nini=n;
if(n==m) System.out.println(n);
else{
while(n>0)

{
n=n-jour;
if(n>0) {n=n+m;jour++;}
if(n>nini) n=nini;
}
System.out.println(jour);
}
}
public static void main(String[] args) {
new C785();

}

}

par exemple j'entre 5 1 et il m'affiche 4
merci pour ta réponse
KX 15101 Messages postés samedi 31 mai 2008Date d'inscriptionModérateurStatut 18 décembre 2017 Dernière intervention - 16 mars 2017 à 20:59
Ce problème peut se résoudre sans boucle. Il faut cependant le traiter de manière mathématiques pour calculer le résultat exact.

Il faut distinguer deux périodes dans l'histoire :

1) dans les M premiers jours, il y a moins de M oiseaux, donc vu que l'on ramène M graines pour remplir la grange elle sera toujours pleine au moment où les oiseaux viennent manger.

2) après les M premiers jours, les oiseaux étant plus nombreux, ils mangent plus que ce qui n'est ramené chaque jour et on perd X graines au jour M+X

Cela revient donc à perdre 1+2+3+4+...+X qui vaut X(X+1)/2
Voir : Somme des premiers entiers

Au jour M+X où la grange devient vide on a donc N <= X(X+1)/2

De là on doit donc résoudre l'équation X(X+1)/2=N pour trouver X, ce qui donne X=√(8N+1)/2-1/2

Evidemment tout cela reste à vérifier, mais en tout cas il faut oublier ta boucle, la solution à ton problème est mathématique, pas informatique.
Commenter la réponse de KX

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.