IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Python Discussion :

Recuperer plus grand produit


Sujet :

Python

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éclairé Avatar de Neolex
    Homme Profil pro
    Recherche emploi Securité informatique
    Inscrit en
    Avril 2011
    Messages
    243
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Finistère (Bretagne)

    Informations professionnelles :
    Activité : Recherche emploi Securité informatique

    Informations forums :
    Inscription : Avril 2011
    Messages : 243
    Par défaut Recuperer plus grand produit
    j'essaye de faire un exercice d'un site , voici la consigne :

    What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?
    J'ai beau vérifier et re vérifier , je ne vois pas où est le problème dans mon code ...

    le voici :

    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    #!/usr/local/bin/python3.3 
    # -*-coding:utf-8 -*
     
    def GreatestProduct():
    	grid = [[8,2,22,97,38,15,00,40,00,75,4,5,7,78,52,12,50,77,91,8],
    [49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,4,56,62,00],
    [81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,3,49,13,36,65],
    [52,70,95,23,4,60,11,42,69,24,68,56,1,32,56,71,37,2,36,91],
    [22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80],
    [24,47,32,60,99,3,45,2,44,75,33,53,78,36,84,20,35,17,12,50],
    [32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70],
    [67,26,20,68,2,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21],
    [24,55,58,5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72],
    [21,36,23,9,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95],
    [78,17,53,28,22,75,31,67,15,94,3,80,4,62,16,14,9,53,56,92],
    [16,39,5,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57],
    [86,56,00,48,35,71,89,7,5,44,44,37,44,60,21,58,51,54,17,58],
    [19,80,81,68,5,94,47,69,28,73,92,13,86,52,17,77,4,89,55,40],
    [4,52,8,83,97,35,99,16,7,97,57,32,16,26,26,79,33,27,98,66],
    [88,36,68,87,57,62,20,72,3,46,33,67,46,55,12,32,63,93,53,69],
    [4,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36],
    [20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,4,36,16],
    [20,73,35,29,78,31,90,1,74,31,49,71,48,86,81,16,23,57,5,54],
    [1,70,54,71,83,51,54,69,16,92,33,48,61,43,52,1,89,19,67,48]]
     
     
    	max = 0 
     
    	#Boucle de haut en bas
    	i=0
    	j=0
    	while i<17:
    		while j<20:
    			num = grid[i][j]*grid[i+1][j]*grid[i+2][j]*grid[i+3][j]
    			if num >max:
    				max = num
    			j+=1
    		i+=1
    	# Boucle de bas en haut
    	i=3
    	j=0
    	while i<20:
    		while j<20:
    			num = grid[i][j]*grid[i-1][j]*grid[i-2][j]*grid[i-3][j]
    			if num > max:
    				max = num
    			j+=1
    		i+=1
     
    	#boucle de gauche à droite
    	i=0
    	j=0
    	while i<20:
    		while j<17:
    			num = grid[i][j]*grid[i][j+1]*grid[i][j+2]*grid[i][j+3]
    			if num > max :
    				max = num
    			j+=1
    		i+=1
     
    	#boucle de droite à gauche
    	i=0
    	j=3
    	while i<20:
    		while j<20:
    			num = grid[i][j]*grid[i][j-1]*grid[i][j-2]*grid[i][j-3]
    			if num > max:
    				max =num
    			j+=1
    		i+=1
     
    	#boucle diagonale bas droite
    	i = 0
    	j = 0
    	while i<17:
    		while j<17:
    			num = grid[i][j]*grid[i+1][j+1]*grid[i+2][j+2]*grid[i+3][j+3]
    			if num > max :
    				max = num
    			j+=1
    		i+=1
     
    	#boucle diagonale bas gauche
    	i=0
    	j=3
    	while i<17:
    		while j<20:
    			num = grid[i][j]*grid[i+1][j-1]*grid[i+2][j-2]*grid[i+3][j-3]
    			if num > max:
    				max =num
    			j+=1
    		i+=1
     
     
    	print(str(max))
     
     
    GreatestProduct();

    Je trouve un max inférieur à ce que je devrais trouver , j'ai pourtant l'impression de tester toutes les possibilités ...

  2. #2
    Expert confirmé

    Homme Profil pro
    Inscrit en
    Octobre 2008
    Messages
    4 307
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Octobre 2008
    Messages : 4 307
    Par défaut
    Salut,

    Je me pose une question, pourquoi en lisant une ligne de gauche à droite aurait-tu un résultat différent qu'en la lisant en sens inverse ?

    Exemple avec ta première ligne:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
     
    n = [8,2,22,97,38,15,00,40,00,75,4,5,7,78,52,12,50,77,91,8]
     
    def find_max(l):
        mx = 0
        for i in range(len(l)-3):
            tt = l[i]
            for j in range(i+1, i+4):
                tt *= l[j]
     
            if tt > mx:
                mx = tt
                pos = i
     
        print ">>", pos, mx
     
    find_max(n)
    n.reverse()
    find_max(n)
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    >> 15 4204200
    >> 1 4204200
    Pareil pour la lecture verticale et diagonale, non ?

  3. #3
    Membre éclairé Avatar de Neolex
    Homme Profil pro
    Recherche emploi Securité informatique
    Inscrit en
    Avril 2011
    Messages
    243
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Finistère (Bretagne)

    Informations professionnelles :
    Activité : Recherche emploi Securité informatique

    Informations forums :
    Inscription : Avril 2011
    Messages : 243
    Par défaut
    Oui je viens de me rendre compte de ça il y a environ 15 minutes .
    J'ai donc retiré quelques parties de mon code .
    Par contre je n'ai toujours pas trouvé le problème dans mon code , je crois que je vais arrêter de chercher pour aujourd'hui , je m'y remettrais à tête reposée demain.

    Merci en tout cas !

  4. #4
    Membre éclairé Avatar de Neolex
    Homme Profil pro
    Recherche emploi Securité informatique
    Inscrit en
    Avril 2011
    Messages
    243
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 31
    Localisation : France, Finistère (Bretagne)

    Informations professionnelles :
    Activité : Recherche emploi Securité informatique

    Informations forums :
    Inscription : Avril 2011
    Messages : 243
    Par défaut
    UP , si quelqu'un aurait une idée du problème de mon code , je suis toujours bloqué dessus ....

  5. #5
    Expert confirmé

    Homme Profil pro
    Inscrit en
    Octobre 2008
    Messages
    4 307
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Octobre 2008
    Messages : 4 307
    Par défaut
    Si tu sépares tes opérations, tu verras plus clair, et au moyen de divers print judicieusement placés tu pourras voir évoluer le résultat

    Quelque chose comme ceci:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
     
    GRID = [[8,2,22,97,38,15,00,40,00,75,4,5,7,78,52,12,50,77,91,8],
    [49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,4,56,62,00],
    ...
    [1,70,54,71,83,51,54,69,16,92,33,48,61,43,52,1,89,19,67,48]]
     
    def greatest_product():
        direction = 'horizontal'
        line, column, greatest = get_horizontal_max()
     
        ln, cl, gt = get_vertical_max()
        if gt > greatest:
            direction = 'vertical'
            line, column, greatest = ln, cl, gt
     
        ln, cl, gt = get_diagonal_from_left_max()
        if gt > greatest:
            direction = 'diagonal_from_left'
            line, column, greatest = ln, cl, gt
     
        ln, cl, gt = get_diagonal_from_right_max()
        if gt > greatest:
            direction = 'diagonal_from_right'
            line, column, greatest = ln, cl, gt
     
        return greatest, column, line, direction
     
    def get_horizontal_max():
        mx = 0
        for idx, line in enumerate(GRID):
            for i in range(17):
                tt = l[i]
                for j in range(i+1, i+4):
                    tt *= l[j]
     
                if tt > mx:
                    mx = tt
                    col = i
                    ln = idx
     
        return ln, col, mx
     
    def get_vertical_max():
        mx = 0
        for col in range(20):
            for ln range(17):
     
                ...
     
    def get_diagonal_from_left_max():
        mx =0
     
        ...
     
    def get_diagonal_from_right_max():
        mx = 0
     
        ...
     
    sum_max, posX, posY, direction = greatest_product()
    # sum_max est le produit maximal
    # posX, posY sont les coordonnées du premier nombre de quatre dans la grille
    # direction est le sens dans lequel on a trouvé le nombre
    print "Le nombre maximum %s blabla ..."
    Je te laisse remplir les vides.

  6. #6
    Membre Expert
    Homme Profil pro
    Inscrit en
    Mars 2007
    Messages
    941
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : Mars 2007
    Messages : 941
    Par défaut
    Ca me semble être une bonne occasion d'utiliser numpy, ça.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    grid = [[...]]
    import numpy as np
     
    grid = np.array(grid)
     
    prod2 = grid[:,:-1] * grid[:,1:]
    prod4 = prod2[:,:-2] * prod2[:,2:]
    hmax = np.max(prod4)
    Ca permet de trouver le produit max. en horizontal. Le code pour les 3 autres directions (verticale, diagonale descendante et diagonale montante) est très similaire.

    Remarquez que dans le code ci-dessus, il n'y a que 2 multiplications par élément au lieu de 3 avec la solution naïve.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [2008R2] Recuperer la valeur avec la plus grande date
    Par guigui69 dans le forum Développement
    Réponses: 1
    Dernier message: 01/08/2013, 12h47
  2. [WD14] recuperer le plus grand nombre dans une table
    Par devalender dans le forum WinDev
    Réponses: 6
    Dernier message: 03/11/2010, 20h16
  3. Réponses: 6
    Dernier message: 01/11/2010, 18h40
  4. Recuperer le plus grand, le plus petit et la moyenne !
    Par ksper92 dans le forum Langage SQL
    Réponses: 2
    Dernier message: 05/04/2007, 16h24
  5. [Tableaux] Recuperer le plus grand indice d'un tableau
    Par schnito dans le forum Langage
    Réponses: 4
    Dernier message: 31/01/2006, 20h01

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo