Trouver la première plus longue monotonie

Logiciel & apps Programmation
1

Salut à tous,

J’ai un tableau de 150 entiers, affichés par lignes de 10. J’aimerais vous demander ce qu’il faut faire pour trouver la position où débute la première plus longue monotonie de la liste. :frowning:

Une monotonie dans un tableau d’entiers est une sous-séquence triée de longueur maximale.

voici par, exemple ce tableau de 40 entiers, 10 par ligne:

11 5 41 12 23 15 21 13 8 42
2 33 0 26 32 37 17 35 44 18
1 11 40 47 29 41 32 44 25 50
4 33 10 28 38 14 1 2 16 43

ici la plus longue monotonie commence au rang 13 (0, 26, 32, 37).

10 28 38 (dernière ligne) est aussi une monotonie mais n’est pas la plus longue.

Voici ma méthode Affiche:

public static void Affiche()
	{
		for (int i = 0; i < tab.length; ++i) 
		{  
			System.out.print (tab[i] + " ");  
			if (i % 10 == 9)   
				System.out.println ();  
		}  
	}

Quelqu’un pourrait m’aider?

Merci beaucoup d’avance.

2

En C, ca pourais donner un truc comme ca:


int main() {

	int tab[150] = {11,5,41,12,23,15,21,13,8,42,
			2,33,0,26,32,37,17,35,44,18,
			1,11,40,47,29,41,32,44,25,50,
			4,33,10,28,38,14,1,2,16,43};
	int res[150];
	int pos = 0;
	int maxFound = 0;
	char previousIsOk = 0;
	int count = 0;
	int i;

	// Initialisation du tableau des monotonies:
	for( i = 0; i < 150; i++ ) {
		res[i] = -1;
	}

	// Trouve toutes les monotonies possible ( Suite de nombre croissant ):
	for( i = 0; i < 149; i++ ) {
		if( tab[i] < tab[i+1] ) {
			if( previousIsOk == 0 ) {
				pos=i;
			}
			if( (i+1) - pos > res[pos] ) {
				res[pos] = (i+1) - pos;
			}
			previousIsOk = 1;
		} else {
			previousIsOk = 0;
		}
	}

	// Calcul de la monotonie le plus longue parmit celle trouvée:
	pos = 0;
	for( i = 0; i < 150; i++ ) {
		if( res[i] > maxFound ) {
			maxFound = res[i];
			pos = i;
		}
	}

	// Affichage:
	for( i = 0; i < 150; i++ ) {
		if( i % 10 == 0 ) {
			printf("| %3d", tab[i] );
		}
		printf( " | %3d |", tab[i] );
		if( i % 10 == 9 ) {
			printf( " %3d |\n", tab[i] );
		}
	}

	printf( "Suite de %d nombres à la position %d\n", maxFound+1, pos+1 ); // +1 car pour donner des index commencant par 1

	return 0;
}

Je dit pas que c’est la meilleur solution, ya peut etre plus simple.
Edité le 04/04/2009 à 20:32

3

Attention une monotonie n’est pas forcément croissante mais peut être décroissante, ce qui complique.
Ceci dit, essaye déjà de résoudre le problème en trouvant la plus longue séquence croissante.