logo Homepage
+  NewbieContest
|-+  Général» Defouloir» Algo du soir, Bonsoir !
Username:
Password:
Pages: [1] 2
  Imprimer  
Auteur Fil de discussion: Algo du soir, Bonsoir !  (Lu 12997 fois)
BAAL

Profil challenge

Classement : 13/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« le: 26 Février 2017 à 22:55:34 »

Dans la même veine que le fil de discussion “Enigme du soir, Bonsoir !”, on peut ici proposer des problèmes de code/algo qui ne sont pas facilement transférables en challenge officiel. Soit car la solution se trouve facilement sur Google, soit parce qu’on peut toujours réussir avec une solution non-optimale si on laisse le code tourner assez longtemps, ou pour d’autres raisons...

Je commence avec un problème pas trop dur:

Codez une fonction qui prend comme argument un array de int, positifs et négatifs, et qui retourne la somme de la sous-séquence qui donne la plus grande somme.
Par exemple:
input = [3, -10, 3, -2, 5, -7]
output = 6 (somme de [3, -2, 5])
Journalisée
pixis
Administrateur

Profil challenge

Classement : 16/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 664


Voir le profil WWW
« #1 le: 27 Février 2017 à 15:20:45 »

Du coup le challenge, c'est de trouver la fonction la plus optimale, j'imagine
Parce que sinon, je te bf toutes les solutions
* pixis siffle

Non mais j'ai une petite idée en tête un peu tordue. Je pense pas qu'elle soit optimale mais je suis curieux de savoir si j'arrive à la mettre en place "simplement". I'll let you know !
Journalisée

Newbie Contest Staff :
Pixis
Statut :
Administrateur
Blog :
hackndo
the lsd
Administrateur

Profil challenge

Classement : 189/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 3096

poulping for fun & profit


Voir le profil WWW
« #2 le: 27 Février 2017 à 17:07:23 »

Question bête, optimale, là, on l'entend dans quel sens ?
Niveau timing, utilisation ressources, taille/compléxité du code, autre ?

Enjoy

The lsd
Journalisée

Newbie Contest Staff :
The lsd - Th3_l5D (IRC)
Statut :
Administrateur
Citation :
Cartésien désabusé : je pense, donc je suis, mais je m'en fous !
pixis
Administrateur

Profil challenge

Classement : 16/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 664


Voir le profil WWW
« #3 le: 27 Février 2017 à 17:27:24 »

Je pensais à complexité en temps, mais effectivement, il faudrait aussi optimiser la complexité en mémoire.
Journalisée

Newbie Contest Staff :
Pixis
Statut :
Administrateur
Blog :
hackndo
BAAL

Profil challenge

Classement : 13/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« #4 le: 27 Février 2017 à 17:31:13 »

On entend complexité espace/temps asymptotique. Temps la plupart du temps.
Dans le cas de la question ci-dessus, un algo "bête" trouve la réponse en temps O(n^2), mais on peut faire mieux!
Journalisée
harvey

Profil challenge

Classement : 12/54254

Membre Senior
****
Hors ligne Hors ligne
Messages: 316


Voir le profil WWW
« #5 le: 27 Février 2017 à 18:19:51 »

En O(n):
 
def plus_grande_somme2(sequence, defaut=float("-inf")):
    #defaut: valeur de la séquence vide
    somme=0
    meilleure_somme=defaut
    for val in sequence:
        somme = max(somme+val, val)
        meilleure_somme = max(meilleure_somme, somme)
    return meilleure_somme

« Dernière édition: 27 Février 2017 à 23:40:20 par harvey » Journalisée

L'entropie vient en mangeant.
BAAL

Profil challenge

Classement : 13/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« #6 le: 28 Février 2017 à 04:18:11 »

J’ai fait ça un peu différemment, ton code est plus compact, mais il m’a l’air bon! J’aime bien les problèmes où on passe de O(n^2) à O(n) en réfléchissant un peu .
Journalisée
BAAL

Profil challenge

Classement : 13/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« #7 le: 05 Mars 2017 à 02:26:08 »

Un peu plus compliqué cette fois-ci: On cherche une fonction qui reçoit un array de nombres entiers positifs et retourne le nombre qu’on retrouve le plus de fois dans l’array, s’il y est au moins 50% du temps. Sinon on retourne -1.
Exemple:
input = [1, 5, 3, 2, 3, 10, 3, 3, 3]
output = 3
input = [1, 5, 3, 2, 3, 10, 3, 3, 4]
output = -1
La solution doit être en temps O(n) et espace O(1).
Journalisée
harvey

Profil challenge

Classement : 12/54254

Membre Senior
****
Hors ligne Hors ligne
Messages: 316


Voir le profil WWW
« #8 le: 06 Mars 2017 à 00:54:02 »

L'énoncé ne précise pas que faire quand deux éléments forment 50% du tableau chacun.
Je suppose qu'on doit retourner -1.

Je pense avoir une solution en O(n) en moyenne.

La taille du tableau est N.
Initialiser les bornes bmin = 0, bmax = infini
Boucle:
-choisir un élément du tableau au hasard (= p) tel que bmin < p < bmax
-compter le nombre d'éléments x (bmin < x < bmax) supérieurs, égaux et inférieurs à p
    -si aucun de ces ensembles n'est de taille supérieure ou égale à N/2:
     retourner -1
    -si l'ensemble d'éléments égaux à p est de taille >= N/2:
            -si partage 50/50, retourner -1, sinon retourner p
    -sinon, poser bmin = p (si l'ensemble supérieur à p est le plus gros),
    ou bmax = p (si l'ensemble inférieur est le plus gros), et boucler

Il y a 7 variables (mémoire constante). Le temps est N^2 dans le pire des cas
(si chaque itération n'élimine qu'un seul élément), mais N en général.
Le nombre d'itérations moyen ne dépend pas des paramètres (c'est proche de 3
quand tous les éléments sont différents).



Si, comme je l'ai lu quelque part, il existe un algo pour trouver la médiane
en O(n) dans le pire des cas, il est certainement possible d'améliorer.
« Dernière édition: 06 Mars 2017 à 14:39:57 par harvey » Journalisée

L'entropie vient en mangeant.
BAAL

Profil challenge

Classement : 13/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« #9 le: 06 Mars 2017 à 18:31:16 »

J'aime bien ton idée, mais on peut faire mieux: O(n) dans le pire des cas!
Journalisée
BAAL

Profil challenge

Classement : 13/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« #10 le: 12 Mars 2017 à 23:43:44 »

Rien à voir avec la médiane d'ailleurs.
Cette question n'est vraiment pas si difficile, ça ne devrait pas prendre plus de quelques minutes.
Journalisée
pixis
Administrateur

Profil challenge

Classement : 16/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 664


Voir le profil WWW
« #11 le: 13 Mars 2017 à 09:21:48 »

Hello,
J'ai cherché une solution, mais ta condition "s’il y est au moins 50% du temps" me bloque. J'ai trouvé du O(n) pour le cas de majorité absolue, mais lorsque j'arrive à des cas où la majorité est tout pile 50%, je me retrouve avec le dernier élément qui sort de mon algo au lieu de l'élément présent à 50%, et je ne vois pas comment le contourner. Je pense que je dois trouver une autre manière de faire parce que là je suis un peu dans une impasse.

Je continue de réfléchir du coup avant de poster ma solution.
Journalisée

Newbie Contest Staff :
Pixis
Statut :
Administrateur
Blog :
hackndo
harvey

Profil challenge

Classement : 12/54254

Membre Senior
****
Hors ligne Hors ligne
Messages: 316


Voir le profil WWW
« #12 le: 22 Mars 2017 à 12:35:38 »

J'ai cherché une solution, mais ta condition "s’il y est au moins 50% du temps" me bloque. J'ai trouvé du O(n) pour le cas de majorité absolue, mais lorsque j'arrive à des cas où la majorité est tout pile 50%, je me retrouve avec le dernier élément qui sort de mon algo au lieu de l'élément présent à 50%, et je ne vois pas comment le contourner.
Ton algorithme fonctionne dans tous les cas si la longueur du tableau est impaire. Dans le cas où elle est paire, il suffirait de compter le nombre d'occurrences du premier élément, et s'il n'est pas majoritaire d'appliquer l'algo à partir du second. Ça reste dans la borne O(n).
Journalisée

L'entropie vient en mangeant.
Alkanor

Profil challenge

Classement : 3/54254

Membre Junior
**
Hors ligne Hors ligne
Messages: 59


Voir le profil
« #13 le: 22 Mars 2017 à 15:36:35 »

En O(n log(n)) temps et O(1) espace on peut se contenter de trier le tableau et de compter ensuite.

Edit : d'ailleurs par rapport à la complexité spatiale, est-ce qu'on considère que modifier le tableau initial (chaque case) génère une  complexité spatiale O(n) ou bien on reste en O(1) ? (dans le premier cas d'ailleurs le tri serait alors en O(n) spatialement)

Edit2 : je pense avoir trouvé quelque chose qui marche : on crée une sorte d'échelle sur l'élément majoritaire : on parcourt le tableau une fois, pour chaque élément, soit c'est le même élément que celui qui est associé à l'échelle actuellement et on monte d'une case, soit ça n'est pas le cas et on descend d'une case. Si l'échelle est vide (comme au début de l'algo par exemple), on change l'élément associé à l'échelle par l'élément actuel. A la fin on obtient un élément qui correspond au seul majoritaire possible. Mais ça n'est pas sûr que c'en soit effectivement un. Il suffit de refaire un parcours du tableau en comptant l'élément trouvé à la fin et en vérifiant qu'il est bien présent dans une quantité supérieure à la moitié de la taille du tableau.
« Dernière édition: 22 Mars 2017 à 16:22:44 par Alkanor » Journalisée
pixis
Administrateur

Profil challenge

Classement : 16/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 664


Voir le profil WWW
« #14 le: 22 Mars 2017 à 16:26:02 »

Merci Harvey. Mon code est sale mais je crois qu'il marche et qu'il est O(n) en temps si je ne me trompe pas. En revanche il esy O(n2) en espace il me semble ... Je dois pouvoir le faire sans récursion

Code: (python)
def maj(l, next_n=-1, count=0):
   
    if next_n == -1:
        return maj(l, l[0], 0)

    # Si liste paire et premier element majoritaire, on le retourne sinon on retourne la même fonction sans le premier element
    if len(l) % 2 == 0:
        if 2*l.count(l[0]) == len(l):
            return l[0]
        else:
            return maj(l[1:])

    for k,n in enumerate(l):
        """
        L'idée c'est qu'on cherche un élément strictement majoritaire.
        Donc si on parcourt la liste élément par élément en créant une sorte de liste temporaire
        On regarde dans cette liste temporaire s'il y a un element en majorité, qu'on garde quand on augmente la liste
        S'il n'y a pas de majorité, ça veut dire qu'il faut qu'il y ait une majorité dans le reste de la liste.

        Pour le premier element, il est seul dans la liste, donc il est majoritaire, il y en a 1 de plus de le reste.
        Si on ajoute le deuxieme element
        -> Si c'est le même alors il est majoritaire avec une majorité de 2 de plus que le rest
        -> Si c'est pas le même alors il n'est pas majoritaire, et on réduit le décompte. Ici, le compte arrive à 0, et on rappelle la fonction avec le reste de la liste

        Et ainsi de suite.
        Si le compte arrive à zéro, alors on renvoie le reste de la liste et on prend le premier élément comme majoritaire car
        de toute façon dans les éléments précédents, il n'y a pas de majorité absolue, donc ce qui compte, c'est la majorité absolue dans ce qui reste.

        Exemple :
        l=[1,2,1,3,2,1,1]

        On prend "1", qu'on considère majoritaire dans l[:1] avec count = 1
        Ensuite on prend 2, différent de la majorité actuelle donc count = 0 dans l[:2].
        Comme count = 0, on se fiche de l[:2] finalement, aucune majorité ne s'en dégage. Donc on veut un majorité dans l[2:]
        Donc on rappelle la fonction avec l[2:]

        Ca va etre rappelé avec [1,3,2,1,1] puis [2,1,1] puis [1] donc l'élément potentiellement majoritaire est 1. Il est vérifié dans get_maj
        """
        if count == 0:
            return maj(l[k:], n, 1)
        elif count != 0 and next_n == n:
            count += 1
        else:
            count -= 1
    if l.count(next_n)*2 >= len(l):
        return next_n
    else:
        return -1

"""
Quand on a un élément potentiel, on le compte, et on vérifie qu'il est bon
"""
def get_maj(l):
    if l.count(maj(l))*2 >= len(l):
        return maj(l)
    else:
        return -1

edit : Ah bah oui je peux le faire sans récursion et là c'est O(n) temps et 0(n) espace (sauf que je pense pas avoir compris la complexité espace, ya forcément besoin de O(n) pour une liste de longueur n non ?)

Code: (python)
def maj(l):
    count = 0
    next_n = -1
    if len(l) % 2 == 0:
        if 2*l.count(l[0]) == len(l):
            return l[0]
        else:
            return maj(l[1:])

    for n in l:
        if count == 0:
            next_n, count = n, 1
        elif count != 0 and next_n == n:
            count += 1
        else:
            count -= 1
    if l.count(next_n)*2 >= len(l):
        return next_n
    else:
        return -1

edit 2 : Ah dans ma première version j'étais aussi 0(n2) à cause de ma récursion pour les listes paires. Il fallait que je sorte la comparaison de la fonction, c'est tout.
Journalisée

Newbie Contest Staff :
Pixis
Statut :
Administrateur
Blog :
hackndo
Pages: [1] 2
  Imprimer  
 
Aller à: