[Prog] Cet exo d'algo basique DETROUSSE le 18-25

Le 08 décembre 2018 à 02:12:36 Silencieux_25 a écrit :
J'ai trouvé plus de 12000 pour la taille de la chaîne de caractéres et pas 9300 et quelques

poste ton code source ici

Le 08 décembre 2018 à 01:49:26 GeoFront a écrit :

Le 08 décembre 2018 à 01:45:21 MecHonnete a écrit :
À mon tour :

Vous avez six parts de tarte
Vous en donnez deux à Émile
Combien vous en reste-t-il ?

Faites l'algo

Bah si Emile il est pas content il chourrave toute la tarte et nous on a plus rien

Tu peux te battre avec Émile
Ça devient un problème de théorie microéconomique

Tu as 6 parts de tartes, et tu en donnes deux à Émile
Émile est associé à une probabilité p pour laquelle il est content
Si l'événement Émile_content se réalise, Émile est associé à une probabilité q qu'il n'ait plus faim, et pour (1-q) il demande une nouvelle part de tarte
Si Émile est content et qu'il n'a plus faim, il part
Si Émile est content mais qu'il a encore faim, il te demande une nouvelle part si son coefficient de réserve mu est strictement inférieur à 0.4, pour mu compris entre 0 et 1 appartenant à R
Si Émile est content, qu'il a encore faim et pour mu >= 0.4, il part
Si Émile est content, qu'il a encore faim et pour mu < 0.4, il demande une nouvelle part, tu as le choix d'accepter ou de refuser : si tu refuses, Émile a le choix de se battre pour sa part, ou de repartir le ventre vide, cependant tu ne refuses sa part qu'en fonction de ton aversion au combat A, et lui ne la réclame de force qu'en fonction de la sienne B, avec (A,B) appartenant à [0;1]^2
On se place dans un contexte où la fonction d'utilité d'Émile est de la forme sqrt(.), et la tienne ln(.), pour une tarte de valeur v, et une variable aléatoire X qui suit le coût des parts mangées par Émile de loi inconnue

Pour (1-p), Émile n'est vraiment pas content, et demande une nouvelle part de tarte avec une probabilité certaine

Combien de parts de tarte peux-tu espérer avoir quand Émile sera parti ?

Le 08 décembre 2018 à 02:16:38 MecHonnete a écrit :

Le 08 décembre 2018 à 01:49:26 GeoFront a écrit :

Le 08 décembre 2018 à 01:45:21 MecHonnete a écrit :
À mon tour :

Vous avez six parts de tarte
Vous en donnez deux à Émile
Combien vous en reste-t-il ?

Faites l'algo

Bah si Emile il est pas content il chourrave toute la tarte et nous on a plus rien

Tu peux te battre avec Émile
Ça devient un problème de théorie microéconomique

Tu as 6 parts de tartes, et tu en donnes deux à Émile
Émile est associé à une probabilité p pour laquelle il est content
Si l'événement Émile_content se réalise, Émile est associé à une probabilité q qu'il n'ait plus faim, et pour (1-q) il demande une nouvelle part de tarte
Si Émile est content et qu'il n'a plus faim, il part
Si Émile est content mais qu'il a encore faim, il te demande une nouvelle part si son coefficient de réserve mu est strictement inférieur à 0.4, pour mu compris entre 0 et 1 appartenant à R
Si Émile est content, qu'il a encore faim et pour mu >= 0.4, il part
Si Émile est content, qu'il a encore faim et pour mu < 0.4, il demande une nouvelle part, tu as le choix d'accepter ou de refuser : si tu refuses, Émile a le choix de se battre pour sa part, ou de repartir le ventre vide, cependant tu ne refuses sa part qu'en fonction de ton aversion au combat A, et lui ne la réclame de force qu'en fonction de la sienne B, avec (A,B) appartenant à [0;1]^2
On se place dans un contexte où la fonction d'utilité d'Émile est de la forme sqrt(.), et la tienne ln(.), pour une tarte de valeur v, et une variable aléatoire X qui suit le coût des parts mangées par Émile de loi inconnue

Pour (1-p), Émile n'est vraiment pas content, et demande une nouvelle part de tarte avec une probabilité certaine

Combien de parts de tarte peux-tu espérer avoir quand Émile sera parti ?

non mais dans ces cas là autant programmer un système de combat et faire un jeux rpg en mode

Le 08 décembre 2018 à 02:12:36 Silencieux_25 a écrit :
J'ai trouvé plus de 12000 pour la taille de la chaîne de caractéres et pas 9300 et quelques

poste ton code source ici

Le voilà mais j'ai pas eu le temps de le commenter/présenter plus clairement, il tient pas en moins de 10 lignes non plus ^^

<code>import string
import urllib

link = "https://pastebin.com/raw/5QtbiaCd"
f = urllib.urlopen(link)
chaine = f.read()
#chaine = "dabAcCaCBAcCcaDA"
alphabet_minuscule = string.ascii_lowercase
alphabet_majuscule = string.ascii_uppercase
indices = []
indices_a_supprimer = []
liste_chaine = list(chaine)
print(liste_chaine)
print(len(liste_chaine))
compte = 1
while compte == 1:
 compte = 0
 for i in range(0, len(liste_chaine) - 1):
   for j in range(0, len(alphabet_minuscule)):
     if (liste_chaine[i] == alphabet_minuscule[j] and liste_chaine[i + 1] == alphabet_majuscule[j]) or (liste_chaine[i] == alphabet_majuscule[j] and liste_chaine[i + 1]  == alphabet_minuscule[j]):
       if i < len(liste_chaine) - 2:
        if liste_chaine[i + 2] != alphabet_minuscule[j] and liste_chaine[i + 2] != alphabet_minuscule[j]:
         indices.append(i)
         indices.append(i+1)
         compte = 1
       if i == len(liste_chaine) - 2:
        if liste_chaine[i - 2] != alphabet_minuscule[j] and liste_chaine[i - 2] != alphabet_minuscule[j]:
         indices.append(i)
         indices.append(i+1)
         compte = 1
 for indice in indices:
   if indice not in indices_a_supprimer:
     indices_a_supprimer.append(indice)
 
 indices_a_supprimer.reverse()
 for indice in indices_a_supprimer:   
     del liste_chaine[indice]
   
 indices = []
 indices_a_supprimer = []


print(liste_chaine)
print("taille de la chaine restante : ",len(liste_chaine))</code>

Le 08 décembre 2018 à 02:18:16 GeoFront a écrit :

Le 08 décembre 2018 à 02:16:38 MecHonnete a écrit :

Le 08 décembre 2018 à 01:49:26 GeoFront a écrit :

Le 08 décembre 2018 à 01:45:21 MecHonnete a écrit :
À mon tour :

Vous avez six parts de tarte
Vous en donnez deux à Émile
Combien vous en reste-t-il ?

Faites l'algo

Bah si Emile il est pas content il chourrave toute la tarte et nous on a plus rien

Tu peux te battre avec Émile
Ça devient un problème de théorie microéconomique

Tu as 6 parts de tartes, et tu en donnes deux à Émile
Émile est associé à une probabilité p pour laquelle il est content
Si l'événement Émile_content se réalise, Émile est associé à une probabilité q qu'il n'ait plus faim, et pour (1-q) il demande une nouvelle part de tarte
Si Émile est content et qu'il n'a plus faim, il part
Si Émile est content mais qu'il a encore faim, il te demande une nouvelle part si son coefficient de réserve mu est strictement inférieur à 0.4, pour mu compris entre 0 et 1 appartenant à R
Si Émile est content, qu'il a encore faim et pour mu >= 0.4, il part
Si Émile est content, qu'il a encore faim et pour mu < 0.4, il demande une nouvelle part, tu as le choix d'accepter ou de refuser : si tu refuses, Émile a le choix de se battre pour sa part, ou de repartir le ventre vide, cependant tu ne refuses sa part qu'en fonction de ton aversion au combat A, et lui ne la réclame de force qu'en fonction de la sienne B, avec (A,B) appartenant à [0;1]^2
On se place dans un contexte où la fonction d'utilité d'Émile est de la forme sqrt(.), et la tienne ln(.), pour une tarte de valeur v, et une variable aléatoire X qui suit le coût des parts mangées par Émile de loi inconnue

Pour (1-p), Émile n'est vraiment pas content, et demande une nouvelle part de tarte avec une probabilité certaine

Combien de parts de tarte peux-tu espérer avoir quand Émile sera parti ?

non mais dans ces cas là autant programmer un système de combat et faire un jeux rpg en mode

Pie fight 2019, GOTY, 4K 250fps et vous les consoleux ?

Le 08 décembre 2018 à 02:21:59 MecHonnete a écrit :

Le 08 décembre 2018 à 02:18:16 GeoFront a écrit :

Le 08 décembre 2018 à 02:16:38 MecHonnete a écrit :

Le 08 décembre 2018 à 01:49:26 GeoFront a écrit :

Le 08 décembre 2018 à 01:45:21 MecHonnete a écrit :
À mon tour :

Vous avez six parts de tarte
Vous en donnez deux à Émile
Combien vous en reste-t-il ?

Faites l'algo

Bah si Emile il est pas content il chourrave toute la tarte et nous on a plus rien

Tu peux te battre avec Émile
Ça devient un problème de théorie microéconomique

Tu as 6 parts de tartes, et tu en donnes deux à Émile
Émile est associé à une probabilité p pour laquelle il est content
Si l'événement Émile_content se réalise, Émile est associé à une probabilité q qu'il n'ait plus faim, et pour (1-q) il demande une nouvelle part de tarte
Si Émile est content et qu'il n'a plus faim, il part
Si Émile est content mais qu'il a encore faim, il te demande une nouvelle part si son coefficient de réserve mu est strictement inférieur à 0.4, pour mu compris entre 0 et 1 appartenant à R
Si Émile est content, qu'il a encore faim et pour mu >= 0.4, il part
Si Émile est content, qu'il a encore faim et pour mu < 0.4, il demande une nouvelle part, tu as le choix d'accepter ou de refuser : si tu refuses, Émile a le choix de se battre pour sa part, ou de repartir le ventre vide, cependant tu ne refuses sa part qu'en fonction de ton aversion au combat A, et lui ne la réclame de force qu'en fonction de la sienne B, avec (A,B) appartenant à [0;1]^2
On se place dans un contexte où la fonction d'utilité d'Émile est de la forme sqrt(.), et la tienne ln(.), pour une tarte de valeur v, et une variable aléatoire X qui suit le coût des parts mangées par Émile de loi inconnue

Pour (1-p), Émile n'est vraiment pas content, et demande une nouvelle part de tarte avec une probabilité certaine

Combien de parts de tarte peux-tu espérer avoir quand Émile sera parti ?

non mais dans ces cas là autant programmer un système de combat et faire un jeux rpg en mode

Pie fight 2019, GOTY, 4K 250fps et vous les consoleux ?

la rage des pro M des pro S et des pro N se fait entendre

import string import urllib link = "https://pastebin.com/raw/5QtbiaCd" f = urllib.urlopen(link) chaine = f.read() #chaine = "dabAcCaCBAcCcaDA" alphabet_minuscule = string.ascii_lowercase alphabet_majuscule = string.ascii_uppercase indices = [] indices_a_supprimer = [] liste_chaine = list(chaine) print(liste_chaine) print(len(liste_chaine)) compte = 1 while compte == 1: compte = 0 for i in range(0, len(liste_chaine) - 1): for j in range(0, len(alphabet_minuscule)): if (liste_chaine[i] == alphabet_minuscule[j] and liste_chaine[i + 1] == alphabet_majuscule[j]) or (liste_chaine[i] == alphabet_majuscule[j] and liste_chaine[i + 1] == alphabet_minuscule[j]): if i < len(liste_chaine) - 2: if liste_chaine[i + 2] != alphabet_minuscule[j] and liste_chaine[i + 2] != alphabet_minuscule[j]: indices.append(i) indices.append(i+1) compte = 1 if i == len(liste_chaine) - 2: if liste_chaine[i - 2] != alphabet_minuscule[j] and liste_chaine[i - 2] != alphabet_minuscule[j]: indices.append(i) indices.append(i+1) compte = 1 for indice in indices: if indice not in indices_a_supprimer: indices_a_supprimer.append(indice) indices_a_supprimer.reverse() for indice in indices_a_supprimer: del liste_chaine[indice] indices = [] indices_a_supprimer = [] print(liste_chaine) print("taille de la chaine restante : ",len(liste_chaine))

bordel de merde

public static int reducedLength(String line) {
__for (int i = 0; i < line.length; i++)
____for (int j = 0; j < line.length - 1; j++)
______if ((line.charAt(j) == line.charAt(j + 1).toLowerCase && line.charAt(j + 1).isUpperCase) || (line.charAt(j) == line.charAt(j + 1).toUpperCase && line.charAt(j).isUpperCase))
________line = line.subString(0, j - 1) + line.subString(j + 1, line.length - 1);
__return line.length;
}

Indentation avec "__" désolé
Potentiellement pas opti
Mais aucune consigne de l'auteur à ce propos

bordel de merde

dans un premier temps on identifie l'ensemble des mots dont le centre est de rang 2^n et dont dont le mot de taille 2^n dont il en est le centre forme un mot totalement simplifiable
On note M la taille du gros mot et ln le log en base2 et ln_4 log en base 4
A n fixe il y a M/2^n lettre ou des verif sont a faire et la verif prend 2^n temps donc a n fixe on a un temps de M et comme n navigue entre 1 et ln(M) ca fait ln(M)M comme temps.
Dans la suite ce que j'appelle l'algorthime consiste a identife les sous mots simplifiable de la forme decrite au debut puis a les simplifier (une fois tous identifier pas au fur et a mesure que n augmente). Quand je dirai que l'algorithme est repete cela signifie obv qu'il est repete sur la simplification de M obtenue precedement. Dans le calcul de complexite je neglige l'etape qui consiste en l'elaboration du mot simplifie une fois les simplifications de forme definie precedemment identifiees pcq il est tard.
Maintenant je vous laisse verifier (ce que j'ai pas fait mais geometriquement ca me semble bon) que soit X un sous mot totalement simplifiable de taille l et soit p = max{n | 2^n <= l} alors l'algorithme ci dessus identifie un sout mot totalement simplifiable de X de taille 2^p-1 c'est a dire au moin un quart de la taille de X.
X etant au maximum de taille M il faudrait au maximum pour le reduire totalement repete x fois l'algorithme avec x verifiant (M/4)^x = 1 soit x = ln_4(M). D'ou une complexite en ln(M)ln_4(M)M.

J'ai presque jamais fait d'info donc je dis peut etre de la merde.

Le 08 décembre 2018 à 02:42:53 F2P_2LaNuit a écrit :
dans un premier temps on identifie l'ensemble des mots dont le centre est de rang 2^n et dont dont le mot de taille 2^n dont il en est le centre forme un mot totalement simplifiable
On note M la taille du gros mot et ln le log en base2 et ln_4 log en base 4
A n fixe il y a M/2^n lettre ou des verif sont a faire et la verif prend 2^n temps donc a n fixe on a un temps de M et comme n navigue entre 1 et ln(M) ca fait ln(M)M comme temps.
Dans la suite ce que j'appelle l'algorthime consiste a identife les sous mots simplifiable de la forme decrite au debut puis a les simplifier (une fois tous identifier pas au fur et a mesure que n augmente). Quand je dirai que l'algorithme est repete cela signifie obv qu'il est repete sur la simplification de M obtenue precedement. Dans le calcul de complexite je neglige l'etape qui consiste en l'elaboration du mot simplifie une fois les simplifications de forme definie precedemment identifiees pcq il est tard.
Maintenant je vous laisse verifier (ce que j'ai pas fait mais geometriquement ca me semble bon) que soit X un sous mot totalement simplifiable de taille l et soit p = max{n | 2^n <= l} alors l'algorithme ci dessus identifie un sout mot totalement simplifiable de X de taille 2^p-1 c'est a dire au moin un quart de la taille de X.
X etant au maximum de taille M il faudrait au maximum pour le reduire totalement repete x fois l'algorithme avec x verifiant (M/4)^x = 1 soit x = ln_4(M). D'ou une complexite en ln(M)ln_4(M)M.

J'ai presque jamais fait d'info donc je dis peut etre de la merde.

la premiere phrase j'ai melange deux formulation, il faut lire: *dans un premier temps on identifie l'ensemble des mots totalement simplifiable de taille 2^n dont le centre est de rang de la forme k*2^n

dsl

edit: bordel

La fac d'info, ça apprends des algo inutiles, par contre dès que faut faire de la POO, ils sont plus là

Dut > licence

Le 08 décembre 2018 à 13:44:12 KheyVaniteux a écrit :
La fac d'info, ça apprends des algo inutiles, par contre dès que faut faire de la POO, ils sont plus là

Dut > licence

Ok le pisseur de codent

Enfin obtenu les 9359

#coding: utf-8
import urllib
#on recupere le texte du lien 
link = "https://pastebin.com/raw/5QtbiaCd"
f = urllib.urlopen(link)
chaine = f.read()
#chaine = "dabAcCaCBAcCcaDA" # : on peut utiliser cet exemple là

#on cree une liste a partir de la chaine de caractere
liste_chaine = list(chaine)

#liste pour stocker les indices des lettres a supprimer
liste_indices = []

#liste pour supprimer les occurences des indices a supprimer
liste_indices_a_supprimer = []

#liste pour verrouiller certains indices : exemple : "acCcB" --> le 3eme c ne doit pas etre supprimé
liste_indices_verrou = []

compte = 1

#Tant que compte est egal à 1 on fait un passage sur la liste liste_chaine
while compte == 1:
 compte = 0

 #On boucle sur toute la chaine de caracteres 
 for i in range(0, len(liste_chaine) - 1): 
   # condition IF lorsque les lettres sont les mêmes mais avec une casse différente 
   if liste_chaine[i].lower() == liste_chaine[i + 1].lower() and liste_chaine[i] != liste_chaine[i + 1]:
    
     #Si i n'est pas dans les indices "verrouillés" alors la condition est verifiée 
     if i not in liste_indices_verrou:
      #on ajoute dans la liste liste_indices les indices des elements que l'on va supprimer
      liste_indices.append(i)
      liste_indices.append(i + 1)
      liste_indices_verrou.append(i + 1)
      
      compte = 1 #si la condition IF n'est pas verifiee alors on sortira de la boucle While 
 
 # on copie les indices de liste_indices dans liste_indices_a_supprimer avec une seule occurence pour chaque indice 
 for indice in liste_indices: 
    if indice not in liste_indices_a_supprimer:
        liste_indices_a_supprimer.append(indice)

 # on inverse la liste des indices des elements a supprimer car il faut
 # supprimer en commençant par la fin pour ne pas avoir d'index out of range
 liste_indices_a_supprimer.reverse()
 
 #on supprime enfin les elements en trop
 for indice in liste_indices_a_supprimer:
    del liste_chaine[indice]

#on reinitialise les listes 
 liste_indices = []
 liste_indices_a_supprimer = []
 liste_indices_verrou = []

#on affiche la liste de caractéres ainsi obtenue ainsi que sa taille 
print(liste_chaine)
print(len(liste_chaine))

Je trouve 8971