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

7 décembre 2018 à 23:54:59

Le 07 décembre 2018 à 23:53:14 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:49:25 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:48:27 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:46:16 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:44:55 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:43:32 KheyAuxPommes a écrit :
Ca me fait marrer ceux qui pensent que c'est trivial.
Toujours aucune implémentation 20 min plus tard.
Mais tu veux quoi en fait ?
La soluce avec du code ou juste un algo format texte ?
Pseudo-code ça me va, l'implémentation c'est mieux bien sûr.
Super-lol
20 euros paypal je te fais ton devoir
Même si je suis sûr qu'il y a bien un khey qui voudra bien retirer sa main de son calbute pour te le faire gratos
Mais qu'est-ce tu dis toi ?
Le 07 décembre 2018 à 23:48:43 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:46:53 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:46:00 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:39:00 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:36:15 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:34:36 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:32:13 stuckRANG3 a écrit :
J'ecrirais pas l'algo en entier, mais en gros tu fais une boucle for, t'a une variable X qui stocke depuis quand t'es sur la même lettre, quand tu change de lettre tu regarde X :
- si X vaut 1 la lettre étais toute seule, tu remet X a 0 et tu continue
- si X > 1, y'a des lettres consécutives, tu vire la partie de la liste depuis X élément avant ta position actuelle
Quand est-ce que tu incrémentes X ?
A chaque fois que la lettre actuelle est la même que la precedente
Comment ton algo procède sur AbBa ?
Il faut réitérer l'algo tant que y'a eu des modifications
Et voilà pourquoi ça me fait marrer ceux qui disent que c'est trivial...
Donne nous donc ta solution efficace
A quoi servirait le topic ?...
En soit ce que j'ai dit c'est en O(n^2) dans le pire des cas
Donne au moins ta complexité

Bah non.

PinkHair--

7 décembre 2018 à 23:55:44

Le 07 décembre 2018 à 23:50:32 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:49:51 PinkHair-- a écrit :
Je peux participer ? Je suis un L1 de la fac de Dijon, on pourra comparer nos facs comme ça eh eh
Ah oui je me souviens de toi. T'as peut-être le niveau pour cet exo.

Peut être pas ce soir, je donnais un cours particulier à un M1 à l'autre bout de Paris, je te raconte pas la galère

J'ai une petite idée de l'algo, je démarre spyder pour tester

stuckRANG3

7 décembre 2018 à 23:55:58

Le 07 décembre 2018 à 23:54:59 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:53:14 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:49:25 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:48:27 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:46:16 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:44:55 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:43:32 KheyAuxPommes a écrit :
Ca me fait marrer ceux qui pensent que c'est trivial.
Toujours aucune implémentation 20 min plus tard.
Mais tu veux quoi en fait ?
La soluce avec du code ou juste un algo format texte ?
Pseudo-code ça me va, l'implémentation c'est mieux bien sûr.
Super-lol
20 euros paypal je te fais ton devoir
Même si je suis sûr qu'il y a bien un khey qui voudra bien retirer sa main de son calbute pour te le faire gratos
Mais qu'est-ce tu dis toi ?
Le 07 décembre 2018 à 23:48:43 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:46:53 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:46:00 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:39:00 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:36:15 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:34:36 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:32:13 stuckRANG3 a écrit :
J'ecrirais pas l'algo en entier, mais en gros tu fais une boucle for, t'a une variable X qui stocke depuis quand t'es sur la même lettre, quand tu change de lettre tu regarde X :
- si X vaut 1 la lettre étais toute seule, tu remet X a 0 et tu continue
- si X > 1, y'a des lettres consécutives, tu vire la partie de la liste depuis X élément avant ta position actuelle
Quand est-ce que tu incrémentes X ?
A chaque fois que la lettre actuelle est la même que la precedente
Comment ton algo procède sur AbBa ?
Il faut réitérer l'algo tant que y'a eu des modifications
Et voilà pourquoi ça me fait marrer ceux qui disent que c'est trivial...
Donne nous donc ta solution efficace
A quoi servirait le topic ?...
En soit ce que j'ai dit c'est en O(n^2) dans le pire des cas
Donne au moins ta complexité
Bah non.

L'op qui a pas mieux que O(n^2) :rire:

Nancy_Reyes

7 décembre 2018 à 23:57:07

Détroussey

KheyAuxPommes

7 décembre 2018 à 23:57:35

Le 07 décembre 2018 à 23:55:58 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:54:59 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:53:14 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:49:25 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:48:27 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:46:16 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:44:55 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:43:32 KheyAuxPommes a écrit :
Ca me fait marrer ceux qui pensent que c'est trivial.
Toujours aucune implémentation 20 min plus tard.
Mais tu veux quoi en fait ?
La soluce avec du code ou juste un algo format texte ?
Pseudo-code ça me va, l'implémentation c'est mieux bien sûr.
Super-lol
20 euros paypal je te fais ton devoir
Même si je suis sûr qu'il y a bien un khey qui voudra bien retirer sa main de son calbute pour te le faire gratos
Mais qu'est-ce tu dis toi ?
Le 07 décembre 2018 à 23:48:43 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:46:53 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:46:00 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:39:00 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:36:15 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:34:36 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:32:13 stuckRANG3 a écrit :
J'ecrirais pas l'algo en entier, mais en gros tu fais une boucle for, t'a une variable X qui stocke depuis quand t'es sur la même lettre, quand tu change de lettre tu regarde X :
- si X vaut 1 la lettre étais toute seule, tu remet X a 0 et tu continue
- si X > 1, y'a des lettres consécutives, tu vire la partie de la liste depuis X élément avant ta position actuelle
Quand est-ce que tu incrémentes X ?
A chaque fois que la lettre actuelle est la même que la precedente
Comment ton algo procède sur AbBa ?
Il faut réitérer l'algo tant que y'a eu des modifications
Et voilà pourquoi ça me fait marrer ceux qui disent que c'est trivial...
Donne nous donc ta solution efficace
A quoi servirait le topic ?...
En soit ce que j'ai dit c'est en O(n^2) dans le pire des cas
Donne au moins ta complexité
Bah non.
L'op qui a pas mieux que O(n^2)

Mais putain réfléchis, je me ferais pas chier à faire ce topic si la solution optimale était triviale, je savais que vous alliez partir sur du O(n²) alors qu'il y a mieux.

Edit : La solution optimale n'a rien de compliqué ceci-dit, c'est juste que c'est pas aussi bourrin que ta proposition.

[Ban2]PTSI-PT

7 décembre 2018 à 23:58:15

[23:53:51] <KheyAuxPommes>
Le 07 décembre 2018 à 23:47:34 [Ban2]PTSI-PT a écrit :
[23:45:04] <KheyAuxPommes>
Le 07 décembre 2018 à 23:42:45 [Ban2]PTSI-PT a écrit :
[23:39:31] <KheyAuxPommes>
Le 07 décembre 2018 à 23:38:13 SorrowHill a écrit :
J'avais oublié à quel point les algos du début sont nuls...
Fais le, 5 min chrono en main alors pour le challenge.
Khey il a raison c'est à chier hein
Ça c'est un problème à la fois abordable et intéressant : https://projecteuler.net/problem=82
Algo classique de programmation dynamique.
C'est pas le même niveau que mon exo c'est sûr.
Regarde la taille du fichier texte, il faut être malin, appliquer Dijkstra ou un algo classique fonctionne mais c'est trop long, tu es sensé résoudre en moins de 3 secondes de temps d'exécution
Le 07 décembre 2018 à 23:47:34 [Ban2]PTSI-PT a écrit :
[23:45:04] <KheyAuxPommes>
Le 07 décembre 2018 à 23:42:45 [Ban2]PTSI-PT a écrit :
[23:39:31] <KheyAuxPommes>
Le 07 décembre 2018 à 23:38:13 SorrowHill a écrit :
J'avais oublié à quel point les algos du début sont nuls...
Fais le, 5 min chrono en main alors pour le challenge.
Khey il a raison c'est à chier hein
Ça c'est un problème à la fois abordable et intéressant : https://projecteuler.net/problem=82
Algo classique de programmation dynamique.
C'est pas le même niveau que mon exo c'est sûr.
Regarde la taille du fichier texte, il faut être malin, appliquer Dijkstra ou un algo classique fonctionne mais c'est trop long, tu es sensé résoudre en moins de 3 secondes de temps d'exécution
Il n'y a pas besoin de Dijkstra.
C'est juste que pour trouver la solution avec ta matrice de taille N, tu passes par la solution avec la matrice de taille N - 1 comme s'il y avait une colonne en moins.
Ça se résout bien en programmation dynamique je dirais.

Sauf qu'il n'y a pas qu'une sous-matrice de taille N-1 à considérer mais 2, la complexité est en au mieux en 2^N... :hap:
(Ou alors j'ai mal compris ce que tu veux faire)

On peut résoudre le problème en O(N^2)

AzaPlop

7 décembre 2018 à 23:58:35

Allez je le tente pour le fun

KheyAuxPommes

7 décembre 2018 à 23:59:14

Le 07 décembre 2018 à 23:58:35 AzaPlop a écrit :
Allez je le tente pour le fun

Après 40 min peut-être que tu seras le 1er à proposer une solution.

PlateauDeSaclay

7 décembre 2018 à 23:59:19

Le 07 décembre 2018 à 23:57:35 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:55:58 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:54:59 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:53:14 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:49:25 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:48:27 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:46:16 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:44:55 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:43:32 KheyAuxPommes a écrit :
Ca me fait marrer ceux qui pensent que c'est trivial.
Toujours aucune implémentation 20 min plus tard.
Mais tu veux quoi en fait ?
La soluce avec du code ou juste un algo format texte ?
Pseudo-code ça me va, l'implémentation c'est mieux bien sûr.
Super-lol
20 euros paypal je te fais ton devoir
Même si je suis sûr qu'il y a bien un khey qui voudra bien retirer sa main de son calbute pour te le faire gratos
Mais qu'est-ce tu dis toi ?
Le 07 décembre 2018 à 23:48:43 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:46:53 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:46:00 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:39:00 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:36:15 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:34:36 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:32:13 stuckRANG3 a écrit :
J'ecrirais pas l'algo en entier, mais en gros tu fais une boucle for, t'a une variable X qui stocke depuis quand t'es sur la même lettre, quand tu change de lettre tu regarde X :
- si X vaut 1 la lettre étais toute seule, tu remet X a 0 et tu continue
- si X > 1, y'a des lettres consécutives, tu vire la partie de la liste depuis X élément avant ta position actuelle
Quand est-ce que tu incrémentes X ?
A chaque fois que la lettre actuelle est la même que la precedente
Comment ton algo procède sur AbBa ?
Il faut réitérer l'algo tant que y'a eu des modifications
Et voilà pourquoi ça me fait marrer ceux qui disent que c'est trivial...
Donne nous donc ta solution efficace
A quoi servirait le topic ?...
En soit ce que j'ai dit c'est en O(n^2) dans le pire des cas
Donne au moins ta complexité
Bah non.
L'op qui a pas mieux que O(n^2)
Mais putain réfléchis, je me ferais pas chier à faire ce topic si la solution optimale était triviale, je savais que vous alliez partir sur du O(n²) alors qu'il y a mieux.
Edit : La solution optimale n'a rien de compliqué ceci-dit, c'est juste que c'est pas aussi bourrin que ta proposition.

O(n) en épurant au fur et à mesure non ? Une fois qu'on a vérifié les premiers caractères en changer à droite change rien à gauche

KheyAuxPommes

8 décembre 2018 à 00:02:29

Le 07 décembre 2018 à 23:59:19 PlateauDeSACLAY a écrit :
Le 07 décembre 2018 à 23:57:35 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:55:58 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:54:59 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:53:14 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:49:25 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:48:27 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:46:16 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:44:55 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:43:32 KheyAuxPommes a écrit :
Ca me fait marrer ceux qui pensent que c'est trivial.
Toujours aucune implémentation 20 min plus tard.
Mais tu veux quoi en fait ?
La soluce avec du code ou juste un algo format texte ?
Pseudo-code ça me va, l'implémentation c'est mieux bien sûr.
Super-lol
20 euros paypal je te fais ton devoir
Même si je suis sûr qu'il y a bien un khey qui voudra bien retirer sa main de son calbute pour te le faire gratos
Mais qu'est-ce tu dis toi ?
Le 07 décembre 2018 à 23:48:43 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:46:53 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:46:00 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:39:00 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:36:15 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:34:36 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:32:13 stuckRANG3 a écrit :
J'ecrirais pas l'algo en entier, mais en gros tu fais une boucle for, t'a une variable X qui stocke depuis quand t'es sur la même lettre, quand tu change de lettre tu regarde X :
- si X vaut 1 la lettre étais toute seule, tu remet X a 0 et tu continue
- si X > 1, y'a des lettres consécutives, tu vire la partie de la liste depuis X élément avant ta position actuelle
Quand est-ce que tu incrémentes X ?
A chaque fois que la lettre actuelle est la même que la precedente
Comment ton algo procède sur AbBa ?
Il faut réitérer l'algo tant que y'a eu des modifications
Et voilà pourquoi ça me fait marrer ceux qui disent que c'est trivial...
Donne nous donc ta solution efficace
A quoi servirait le topic ?...
En soit ce que j'ai dit c'est en O(n^2) dans le pire des cas
Donne au moins ta complexité
Bah non.
L'op qui a pas mieux que O(n^2)
Mais putain réfléchis, je me ferais pas chier à faire ce topic si la solution optimale était triviale, je savais que vous alliez partir sur du O(n²) alors qu'il y a mieux.
Edit : La solution optimale n'a rien de compliqué ceci-dit, c'est juste que c'est pas aussi bourrin que ta proposition.
O(n) en épurant au fur et à mesure non ? Une fois qu'on a vérifié les premiers caractères en changer à droite change rien à gauche

Trop abstrait pour moi comme explication, désolé je comprends pas ta méthode.

[Ban2]PTSI-PT

8 décembre 2018 à 00:02:49

[23:59:19] <PlateauDeSACLAY>
Le 07 décembre 2018 à 23:57:35 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:55:58 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:54:59 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:53:14 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:49:25 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:48:27 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:46:16 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:44:55 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:43:32 KheyAuxPommes a écrit :
Ca me fait marrer ceux qui pensent que c'est trivial.
Toujours aucune implémentation 20 min plus tard.
Mais tu veux quoi en fait ?
La soluce avec du code ou juste un algo format texte ?
Pseudo-code ça me va, l'implémentation c'est mieux bien sûr.
Super-lol
20 euros paypal je te fais ton devoir
Même si je suis sûr qu'il y a bien un khey qui voudra bien retirer sa main de son calbute pour te le faire gratos
Mais qu'est-ce tu dis toi ?
Le 07 décembre 2018 à 23:48:43 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:46:53 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:46:00 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:39:00 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:36:15 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:34:36 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:32:13 stuckRANG3 a écrit :
J'ecrirais pas l'algo en entier, mais en gros tu fais une boucle for, t'a une variable X qui stocke depuis quand t'es sur la même lettre, quand tu change de lettre tu regarde X :
- si X vaut 1 la lettre étais toute seule, tu remet X a 0 et tu continue
- si X > 1, y'a des lettres consécutives, tu vire la partie de la liste depuis X élément avant ta position actuelle
Quand est-ce que tu incrémentes X ?
A chaque fois que la lettre actuelle est la même que la precedente
Comment ton algo procède sur AbBa ?
Il faut réitérer l'algo tant que y'a eu des modifications
Et voilà pourquoi ça me fait marrer ceux qui disent que c'est trivial...
Donne nous donc ta solution efficace
A quoi servirait le topic ?...
En soit ce que j'ai dit c'est en O(n^2) dans le pire des cas
Donne au moins ta complexité
Bah non.
L'op qui a pas mieux que O(n^2)
Mais putain réfléchis, je me ferais pas chier à faire ce topic si la solution optimale était triviale, je savais que vous alliez partir sur du O(n²) alors qu'il y a mieux.
Edit : La solution optimale n'a rien de compliqué ceci-dit, c'est juste que c'est pas aussi bourrin que ta proposition.
O(n) en épurant au fur et à mesure non ? Une fois qu'on a vérifié les premiers caractères en changer à droite change rien à gauche

ababababBABABABA
Tu ne peux pas isoler le début car il peut y avoir des grosses réactions en chaîne

Enbadublok

8 décembre 2018 à 00:03:21

Pour moi il faut créer un string pour stocker la chaîne de caractère

comparer deux à deux les cases adjacentes et utiliser le code ascii pour savoir si deux caractères adjacents sont une minuscule et une majuscule

Et si c'est le cas, les supprimer.

Je suis en L3 info et je comprends rien à ce que vous racontez vous parlez de O(n²), de matrices ou je sais pas quoi, je sais même pas ce que ça veut dire

PlateauDeSaclay

8 décembre 2018 à 00:04:22

Le 08 décembre 2018 à 00:02:49 [Ban2]PTSI-PT a écrit :
[23:59:19] <PlateauDeSACLAY>
Le 07 décembre 2018 à 23:57:35 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:55:58 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:54:59 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:53:14 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:49:25 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:48:27 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:46:16 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:44:55 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:43:32 KheyAuxPommes a écrit :
Ca me fait marrer ceux qui pensent que c'est trivial.
Toujours aucune implémentation 20 min plus tard.
Mais tu veux quoi en fait ?
La soluce avec du code ou juste un algo format texte ?
Pseudo-code ça me va, l'implémentation c'est mieux bien sûr.
Super-lol
20 euros paypal je te fais ton devoir
Même si je suis sûr qu'il y a bien un khey qui voudra bien retirer sa main de son calbute pour te le faire gratos
Mais qu'est-ce tu dis toi ?
Le 07 décembre 2018 à 23:48:43 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:46:53 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:46:00 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:39:00 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:36:15 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:34:36 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:32:13 stuckRANG3 a écrit :
J'ecrirais pas l'algo en entier, mais en gros tu fais une boucle for, t'a une variable X qui stocke depuis quand t'es sur la même lettre, quand tu change de lettre tu regarde X :
- si X vaut 1 la lettre étais toute seule, tu remet X a 0 et tu continue
- si X > 1, y'a des lettres consécutives, tu vire la partie de la liste depuis X élément avant ta position actuelle
Quand est-ce que tu incrémentes X ?
A chaque fois que la lettre actuelle est la même que la precedente
Comment ton algo procède sur AbBa ?
Il faut réitérer l'algo tant que y'a eu des modifications
Et voilà pourquoi ça me fait marrer ceux qui disent que c'est trivial...
Donne nous donc ta solution efficace
A quoi servirait le topic ?...
En soit ce que j'ai dit c'est en O(n^2) dans le pire des cas
Donne au moins ta complexité
Bah non.
L'op qui a pas mieux que O(n^2)
Mais putain réfléchis, je me ferais pas chier à faire ce topic si la solution optimale était triviale, je savais que vous alliez partir sur du O(n²) alors qu'il y a mieux.
Edit : La solution optimale n'a rien de compliqué ceci-dit, c'est juste que c'est pas aussi bourrin que ta proposition.
O(n) en épurant au fur et à mesure non ? Une fois qu'on a vérifié les premiers caractères en changer à droite change rien à gauche
ababababBABABABA
Tu ne peux pas isoler le début car il peut y avoir des grosses réactions en chaîne

Quand on est à bB on le vire et on place le curseur à gauche au cas où justement sur le a
Donc je pense pas, mais ptet qu'il peut y avoir de telles réactions oui

[Ban2]PTSI-PT

8 décembre 2018 à 00:05:27

Pour le O(n) il suffit de parcourir la liste une fois pour repérer les paires déjà présentes au début
Puis à chaque fois qu'on supprime une paire, on vérifie si on en créé pas une nouvelle à supprimer en regardant les caractères immédiatement à droite et à gauche

Au pire on fait 2n opérations

PlateauDeSaclay

8 décembre 2018 à 00:07:26

Le 08 décembre 2018 à 00:05:27 [Ban2]PTSI-PT a écrit :
Pour le O(n) il suffit de parcourir la liste une fois pour repérer les paires déjà présentes au début
Puis à chaque fois qu'on supprime une paire, on vérifie si on en créé pas une nouvelle à supprimer en regardant les caractères immédiatement à droite et à gauche
Au pire on fait 2n opérations

Hmm ça a l'air flou. Ca sert à quoi de garder la liste de toutes les paires ?
(C'était inutile pour ce que j'ai proposé)

stuckRANG3

8 décembre 2018 à 00:08:08

Le 08 décembre 2018 à 00:04:22 PlateauDeSACLAY a écrit :
Le 08 décembre 2018 à 00:02:49 [Ban2]PTSI-PT a écrit :
[23:59:19] <PlateauDeSACLAY>
Le 07 décembre 2018 à 23:57:35 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:55:58 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:54:59 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:53:14 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:49:25 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:48:27 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:46:16 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:44:55 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:43:32 KheyAuxPommes a écrit :
Ca me fait marrer ceux qui pensent que c'est trivial.
Toujours aucune implémentation 20 min plus tard.
Mais tu veux quoi en fait ?
La soluce avec du code ou juste un algo format texte ?
Pseudo-code ça me va, l'implémentation c'est mieux bien sûr.
Super-lol
20 euros paypal je te fais ton devoir
Même si je suis sûr qu'il y a bien un khey qui voudra bien retirer sa main de son calbute pour te le faire gratos
Mais qu'est-ce tu dis toi ?
Le 07 décembre 2018 à 23:48:43 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:46:53 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:46:00 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:39:00 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:36:15 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:34:36 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:32:13 stuckRANG3 a écrit :
J'ecrirais pas l'algo en entier, mais en gros tu fais une boucle for, t'a une variable X qui stocke depuis quand t'es sur la même lettre, quand tu change de lettre tu regarde X :
- si X vaut 1 la lettre étais toute seule, tu remet X a 0 et tu continue
- si X > 1, y'a des lettres consécutives, tu vire la partie de la liste depuis X élément avant ta position actuelle
Quand est-ce que tu incrémentes X ?
A chaque fois que la lettre actuelle est la même que la precedente
Comment ton algo procède sur AbBa ?
Il faut réitérer l'algo tant que y'a eu des modifications
Et voilà pourquoi ça me fait marrer ceux qui disent que c'est trivial...
Donne nous donc ta solution efficace
A quoi servirait le topic ?...
En soit ce que j'ai dit c'est en O(n^2) dans le pire des cas
Donne au moins ta complexité
Bah non.
L'op qui a pas mieux que O(n^2)
Mais putain réfléchis, je me ferais pas chier à faire ce topic si la solution optimale était triviale, je savais que vous alliez partir sur du O(n²) alors qu'il y a mieux.
Edit : La solution optimale n'a rien de compliqué ceci-dit, c'est juste que c'est pas aussi bourrin que ta proposition.
O(n) en épurant au fur et à mesure non ? Une fois qu'on a vérifié les premiers caractères en changer à droite change rien à gauche
ababababBABABABA
Tu ne peux pas isoler le début car il peut y avoir des grosses réactions en chaîne
Quand on est à bB on le vire et on place le curseur à gauche au cas où justement sur le a
Donc je pense pas, mais ptet qu'il peut y avoir de telles réactions oui

Ah oui en fait il suffit de faire ça au lieu de reprendre du tout début comme je l'avais fait et c'est bon :rire:

[Ban2]PTSI-PT

8 décembre 2018 à 00:08:35

[00:07:26] <PlateauDeSACLAY>
Le 08 décembre 2018 à 00:05:27 [Ban2]PTSI-PT a écrit :
Pour le O(n) il suffit de parcourir la liste une fois pour repérer les paires déjà présentes au début
Puis à chaque fois qu'on supprime une paire, on vérifie si on en créé pas une nouvelle à supprimer en regardant les caractères immédiatement à droite et à gauche
Au pire on fait 2n opérations
Hmm ça a l'air flou. Ca sert à quoi de garder la liste de toutes les paires ?
(C'était inutile pour ce que j'ai proposé)

Chaque paire à supprimer dans la liste de départ est le début d'une récursion

KheyAuxPommes

8 décembre 2018 à 00:09:21

Le 08 décembre 2018 à 00:08:35 [Ban2]PTSI-PT a écrit :
[00:07:26] <PlateauDeSACLAY>
Le 08 décembre 2018 à 00:05:27 [Ban2]PTSI-PT a écrit :
Pour le O(n) il suffit de parcourir la liste une fois pour repérer les paires déjà présentes au début
Puis à chaque fois qu'on supprime une paire, on vérifie si on en créé pas une nouvelle à supprimer en regardant les caractères immédiatement à droite et à gauche
Au pire on fait 2n opérations
Hmm ça a l'air flou. Ca sert à quoi de garder la liste de toutes les paires ?
(C'était inutile pour ce que j'ai proposé)
Chaque paire à supprimer dans la liste de départ est le début d'une récursion

Il n'y a pas besoin de récursion.

[Ban2]PTSI-PT

8 décembre 2018 à 00:09:27

[00:04:22] <PlateauDeSACLAY>
Le 08 décembre 2018 à 00:02:49 [Ban2]PTSI-PT a écrit :
[23:59:19] <PlateauDeSACLAY>
Le 07 décembre 2018 à 23:57:35 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:55:58 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:54:59 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:53:14 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:49:25 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:48:27 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:46:16 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:44:55 Chien-deter-10 a écrit :
Le 07 décembre 2018 à 23:43:32 KheyAuxPommes a écrit :
Ca me fait marrer ceux qui pensent que c'est trivial.
Toujours aucune implémentation 20 min plus tard.
Mais tu veux quoi en fait ?
La soluce avec du code ou juste un algo format texte ?
Pseudo-code ça me va, l'implémentation c'est mieux bien sûr.
Super-lol
20 euros paypal je te fais ton devoir
Même si je suis sûr qu'il y a bien un khey qui voudra bien retirer sa main de son calbute pour te le faire gratos
Mais qu'est-ce tu dis toi ?
Le 07 décembre 2018 à 23:48:43 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:46:53 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:46:00 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:39:00 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:36:15 stuckRANG3 a écrit :
Le 07 décembre 2018 à 23:34:36 KheyAuxPommes a écrit :
Le 07 décembre 2018 à 23:32:13 stuckRANG3 a écrit :
J'ecrirais pas l'algo en entier, mais en gros tu fais une boucle for, t'a une variable X qui stocke depuis quand t'es sur la même lettre, quand tu change de lettre tu regarde X :
- si X vaut 1 la lettre étais toute seule, tu remet X a 0 et tu continue
- si X > 1, y'a des lettres consécutives, tu vire la partie de la liste depuis X élément avant ta position actuelle
Quand est-ce que tu incrémentes X ?
A chaque fois que la lettre actuelle est la même que la precedente
Comment ton algo procède sur AbBa ?
Il faut réitérer l'algo tant que y'a eu des modifications
Et voilà pourquoi ça me fait marrer ceux qui disent que c'est trivial...
Donne nous donc ta solution efficace
A quoi servirait le topic ?...
En soit ce que j'ai dit c'est en O(n^2) dans le pire des cas
Donne au moins ta complexité
Bah non.
L'op qui a pas mieux que O(n^2)
Mais putain réfléchis, je me ferais pas chier à faire ce topic si la solution optimale était triviale, je savais que vous alliez partir sur du O(n²) alors qu'il y a mieux.
Edit : La solution optimale n'a rien de compliqué ceci-dit, c'est juste que c'est pas aussi bourrin que ta proposition.
O(n) en épurant au fur et à mesure non ? Une fois qu'on a vérifié les premiers caractères en changer à droite change rien à gauche
ababababBABABABA
Tu ne peux pas isoler le début car il peut y avoir des grosses réactions en chaîne
Quand on est à bB on le vire et on place le curseur à gauche au cas où justement sur le a
Donc je pense pas, mais ptet qu'il peut y avoir de telles réactions oui

Je suis d'accord ça marche et c'est plus simple que ce que j'ai proposé

JaiLuLesCGU

8 décembre 2018 à 00:09:50

Où l'auteur a demandé une complexité en O(n) ?

Parcourir la chaîne autant de fois que nécessaire suffit

Données du topic

Auteur: KheyAuxPommes
Date de création: 7 décembre 2018 à 23:25:00
Nb. messages archivés: 282
Nb. messages JVC: 282

En ligne sur JvArchive 252

JvArchive compagnon

Découvrez JvArchive compagnon, le nouvel userscript combattant la censure abusive sur le 18-25 !