Bonjour, je n'arrive pas à optimiser plus que cela mon code, car il est bon mais il n'est pas assez rapide pour les 2 derniers test, merci d'avance

17

3
1 2 2

#include <iostream>
using namespace std;

int main()
{
	int nbPetitsPois; cin >> nbPetitsPois;
	int NbrFactoriels[14] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800};
	int comp = 0, res[14] = {0};
	int i = 1;
	int var = nbPetitsPois;
	while(comp<nbPetitsPois)
	{
		if (var>=NbrFactoriels[i] && var<NbrFactoriels[i+1])
		{
			res[i]++;
			comp+=NbrFactoriels[i];
			var = nbPetitsPois-comp;
			i = 0;
		}
		i++;
	}
	int max;
	for (int i = 14; i > 0; --i)
	{
		if (res[i] != 0)
		{
			cout << i << "\n";
			max = i;
			break;
		}
	}
	for (int i = 1; i <= max; ++i)
	{
		cout << res[i] << " ";
	}
	return 0;
}

-
Edité par Nonoze 7 novembre 2021 à 11:40:18

Nonoze a écrit:

Bonjour, je n'arrive pas à optimiser plus que cela mon code, car il est bon mais il n'est pas assez rapide pour les 2 derniers test, merci d'avance

Ta boucle while est maladroite :

• tu réinitialises i à 0  (et tu repars vraiment à zéro) 
• tu retires factorielle par factorielle donc si le quotient est grand, tu vas trop boucler.

L'algo qui marche ici est l'algo glouton : divise à chaque fois par la plus grande factorielle et recommence avec le reste, tu passeras tous les tests.

-
Edité par PascalOrtiz 7 novembre 2021 à 14:19:42

PascalOrtiz a écrit:

Ta boucle while est maladroite :

• tu réinitialises i à 0  (et tu repars vraiment à zéro) 
• tu retires factorielle par factorielle donc si le quotient est grand, tu vas trop boucler.

L'algo qui marche ici est l'algo glouton : divise à chaque fois par la plus grande factorielle et recommence avec le reste, tu passeras tous les tests.

Ok PascalOrtiz, merci de ta réponse, mais je ne comprends pas le :

"divise à chaque fois par la plus grande factorielle et recommence avec le reste"

Il faut faire quoi concrètement ?

Ps: (merci de prendre du temps pour m'aider sur ce problème, ça fait super plaisir )

Ok, merci PascalOrtiz, j'ai réussis (j'ai juste modifier mon int i = 0, je l'ai remplacer par int i = 13 et i--)

Merci beaucoup

-
Edité par Nonoze 7 novembre 2021 à 20:30:21

Effectivement ce nouveau code passe les tests mais ta boucle while reste vraiment non optimale :

• ton i n'arrête pas de faire des allers et retours pour rien 
• tu répètes une opération qui pourrait se faire en une fois. 

Si on affiche sur cout le flux d'exécution de ton code (voir plus bas), on voit bien qu'il n'est pas optimal :

#include <iostream>
using namespace std;
 
int main()
{
    long int  nbPetitsPois=4*720+3*24;
    long int NbrFactoriels[14] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800};
    int comp = 0, res[14] = {0};
    int i = 13;
    int var = nbPetitsPois;
    while(comp<nbPetitsPois)
    {
        if (var>=NbrFactoriels[i] && var<NbrFactoriels[i+1])
        {
            res[i]++;
            comp+=NbrFactoriels[i];
            var = nbPetitsPois-comp;
            cout << "if "<< i << "\n";
            i = 13;

        }
        i--;
            cout << "while "<< i << "\n";        
    }
    int max;
    for (int i = 13; i > 0; --i)
    {
        if (res[i] != 0)
        {
            cout << i << "\n";
            max = i;
            break;
        }
    }
    for (int i = 1; i <= max; ++i)
    {
        cout << res[i] << " ";
    }
    return 0;
} 

Tu vois que j'ai choisis pour nbPetitsPois=4*6!+3*4! (je note k! factorielle de k)

Pas la peine de répéter le retrait de 6! à nbPetitsPois mais autant calculer son quotient par 6! (tu vas trouver 4) et recommencer l'opération avec la factorielle plus petite suivante sur le reste de la division. Le nouveau quotient sera 3 et le reste nul donc le compte sera bon.

Voici les affichages lus :

while 12
while 11
while 10
while 9
while 8
while 7
while 6
if 6
while 12
while 11
while 10
while 9
while 8
while 7
while 6
if 6
while 12
while 11
while 10
while 9
while 8
while 7
while 6
if 6
while 12
while 11
while 10
while 9
while 8
while 7
while 6
if 6
while 12
while 11
while 10
while 9
while 8
while 7
while 6
while 5
while 4
if 4
while 12
while 11
while 10
while 9
while 8
while 7
while 6
while 5
while 4
if 4
while 12
while 11
while 10
while 9
while 8
while 7
while 6
while 5
while 4
if 4
while 12
6
0 0 0 3 0 4 

Bien sûr, ton code passe les tests parce que les quotients sont petits donc on peut se permettre de répéter.

-
Edité par PascalOrtiz 7 novembre 2021 à 23:10:23

Alors, mais moi je n'ai pas fait i = 13 (pour le 2eme), j'ai fait i++;

regarde mon code :

#include <iostream>
using namespace std;

int main()
{
	int nbPetitsPois; cin >> nbPetitsPois;
	int long long NbrFactoriels[14] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800};
	int comp = 0, res[14] = {0};
	int i = 13;
	int var = nbPetitsPois;
	while(comp<nbPetitsPois)
	{
		if (var>=NbrFactoriels[i] && var<NbrFactoriels[i+1])
		{
			res[i]++;
			comp+=NbrFactoriels[i];
			var = nbPetitsPois-comp;
			i++;
		}
		i--;
	}
	int max;
	for (int i = 13; i > 0; --i)
	{
		if (res[i] != 0)
		{
			cout << i << "\n";
			max = i;
			break;
		}
	}
	for (int i = 1; i <= max; ++i)
		cout << res[i] << " ";
	return 0;
}

-
Edité par Nonoze 8 novembre 2021 à 7:47:34

Nonoze a écrit:

Alors, mais moi je n'ai pas fait i = 13 (pour le 2eme), j'ai fait i++;

regarde mon code :

#include <iostream>
using namespace std;

int main()
{
	int nbPetitsPois; cin >> nbPetitsPois;
	int long long NbrFactoriels[14] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800};
	int comp = 0, res[14] = {0};
	int i = 13;
	int var = nbPetitsPois;
	while(comp<nbPetitsPois)
	{
		if (var>=NbrFactoriels[i] && var<NbrFactoriels[i+1])
		{
			res[i]++;
			comp+=NbrFactoriels[i];
			var = nbPetitsPois-comp;
			i++;
		}
		i--;
	}
	int max;
	for (int i = 13; i > 0; --i)
	{
		if (res[i] != 0)
		{
			cout << i << "\n";
			max = i;
			break;
		}
	}
	for (int i = 1; i <= max; ++i)
		cout << res[i] << " ";
	return 0;
}

-
Edité par Nonoze il y a environ 1 heure

D'accord donc cette fois ton i décroit normalement mais il reste le problème (mineur) de répéter le retrait plutôt que de prendre le quotient. Donc j'aurais plutôt écrit :

#include <iostream>
#include <vector>
using namespace std;

int main() {
  long long nbPetitsPois;
  long long NbrFactoriels[] = {1,       1,        2,         6,         24,
                               120,     720,      5040,      40320,     362880,
                               3628800, 39916800, 479001600, 6227020800};
  vector<int> coeffs{};
  size_t i = 13;
  cin >> nbPetitsPois;
  while (NbrFactoriels[i] > nbPetitsPois)
    i--;
  cout << i << endl;

  while (nbPetitsPois > 0) {
    lldiv_t qr = div(nbPetitsPois, NbrFactoriels[i]);
    coeffs.push_back(qr.quot);
    nbPetitsPois = qr.rem;
    i--;
  }

  for (size_t j = 0; j < i; j++)
    cout << 0 << " ";

  for (size_t j = 0; j < coeffs.size(); j++)
    cout << coeffs[coeffs.size() - j - 1] << " ";

  cout << endl;

  return 0;
}

div sert juste à récupérer en une seule opération le quotient et le reste.

Hein oui, ton code est logique !

Mais comme ils marchent tous les deux, c'est bon