Sujet Précédent Sujet Suivant

Accélerer l'éxécution

Résolu
SMM@ Messages postés 12 Date d'inscription dimanche 7 février 2016 Statut Membre Dernière intervention 15 mars 2018 - Modifié par SMM@ le 16/03/2017 à 01:21
 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

1 réponse

Réponse 1 / 1
KX Messages postés 16703 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 1 juin 2023 126
16 mars 2017 à 07:07
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 ?
0
SMM@ Messages postés 12 Date d'inscription dimanche 7 février 2016 Statut Membre Dernière intervention 15 mars 2018
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
0
KX Messages postés 16703 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 1 juin 2023 126
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.
0
SMM@
16 mars 2017 à 21:25
Merci bq merci merci :)
0
Rejoignez-nous