Top 20

1 0x00h 695 pts
2 boris39 695 pts
3 neoxquick 676 pts
4 maf-ia 658 pts
5 eax 657 pts
6 thefinder 639 pts
7 benito255 604 pts
8 nikokks 597 pts
9 mego 588 pts
10 madbat2 579 pts
11 plucth 561 pts
12 Mart 549 pts
13 Stupefy 529 pts
14 tehron 502 pts
15 Kithyane 497 pts
16 egosum 470 pts
17 rostale 462 pts
18 malose 427 pts
19 CoYoTe99 414 pts
20 Undr 412 pts

Classement complet

Shoutbox

21 Oct - 9:48 pm

Équation du challenge 52 corrigée, merci

16 Oct - 8:43 am

Bonjour, il y a aussi un problème d'affichage "invalid equation" dans le challenge 52. Merci

14 Oct - 8:57 pm

Barbapapou l'équation du challenge 29 a été corrigée

4 Oct - 10:30 am

Bonjour, il y a un problème avec l'affichage d'une équation dans le challenge 29

24 Aug - 7:10 pm

@rostale, en effet l'épreuve 21 ne fonctionne plus depuis un moment, pour l'instant on a pas prévu de temps pour la réparer je pense qu'on va finir par la supprimer tout simplement. @nikokks, ok je t'envoie un mail

22 Aug - 11:40 pm

Salut Metatr0n. pourrait on avoir une discussion en MP. J'imagine que tu as mon mail. Ce serait pour discuter de microcontest en general.

28 Jul - 10:38 pm

Pouvez-vous vérifier l'épreuve Email (21) ? En effet, je ne reçois pas d'email de la part du site. Merci

28 Jul - 7:29 pm

Bonjour et merci. Cependant, j'ai résolu le challenge qui me posait pb, donc plus rien à demander... pour l'instant.

28 Jul - 1:48 pm

Ça devrait être réparé maintenant

28 Jul - 12:04 pm

Bonjour, effectivement j'ai le même message d'erreur, on va investiguer merci d'avoir rapporté le soucis

Connexion
Mot de passe oublié

Supportez nousx

Vous aimez µContest ?
Supportez nous en votant (fun et difficulté) pour µContest sur WeChall :)
Si vous ne l'avez pas encore fait, profitez-en pour lier votre compte
Wechall à µContest pour pouvoir voter !

Merci

Liste des épreuves :: Mathématiques :: Random walk (55)

Résumé

ID : 55
Points : 16
Validations :
Page de l'épreuve
Reporter un bug

Description


Ce qui est traité dans ce challenge a rendu ses créateurs riches et puissants. Ça semble intéressant non ? Voyons de quoi il s'agit.

On va considérer la version la plus simple de l'algorithme. Considérons un graphe de villes avec des liaisons entre certaines d'entre elles :

Imaginez maintenant que quelqu'un décide de voyager dans les différentes villes de manière aléatoire. Au début il est dans une ville et choisit une des liaisons possibles pour aller dans une ville voisine. Toutes les liaisons ont la même probabilité d'être choisies qui est égale à 1/N avec N le nombre de liaisons. Par exemple, il y a trois liaisons partant de D donc la probabilité que le voyageur choisisse l'une d'elles est 1/3. Une fois qu'il arrive dans la ville voisine il recommence le procédé. Et cela indéfiniment.

On définit alors la meilleure ville comme étant la plus visitée par notre voyageur, la deuxième meilleure étant la deuxième plus visitée, etc. L'objectif de ce challenge est d'établir le classement des villes.

Afin d'avoir une description du graphe simple, on le décrit à l'aide d'une matrice, appelée matrice d'adjacence, représentant la probabilité d'aller d'une ville à une autre. Voici un exemple avec le graphe précédent :

Le coefficient rouge représente la probabilité pour le voyageur, lorsqu'il est en B, d'aller en C.

Cependant, pour éviter des problèmes d'approximation, on va simplement mettre des 1 où il y a une liaison :

Ensuite, pour retrouver la matrice de probabilité, vous avez juste à diviser chaque ligne par le nombre de 1 contenus dans celle-ci.

La matrice est codée de la même manière que dans l'épreuve Matrices. Par exemple, la matrice précédente serait codée :
[[0,1,0,0][1,0,1,0][0,1,0,0][1,1,1,0]] dans la variable links.

Le classement doit être renvoyé dans la variable rank avec le format suivant où les villes sont séparées par une virgule, par exemple :
3,4,1,2,5
Ici la ville '3' est la meilleure et la '5' est la pire. Utilisez des chiffres (et non des lettres) de 1 à n, n étant la dimension de la matrice, qui est également le nombre de villes.

Vous n'avez pas trouvé de quoi je parlais au début ? Je vais vous donner un indice (sélectionnez le texte) :
cet algorithme est à l'origine du succès de Google à ses débuts. Et, bien sûr, il n'est pas appliqué aux villes, mais je suis sûr que vous avez deviné ce dont il s'agit !

Exemple



Prenons un exemple. Pour la valeur de variable links suivante : links
Nous attendons le résultat suivant :
rank = "71,7,97,66,55,47,92,5,31,67,94,36,98,35,50,24,21,78,15,81,70,41,9,10,38,100,17,4,73,28,30,37,77,26,12,14,82,68,60,69,42,
76,6,3,59,11,1,89,72,87,58,18,79,63,84,20,39,86,93,29,40,80,96,22,62,54,51,13,8,25,27,91,34,83,64,75,33,19,44,43,52,53,16,
2,95,46,88,32,23,56,74,61,57,48,65,85,45,49,90,99"


Variables


Nom Type Description
Variables à récupérer
linksChaîne de caractèreschar*Matrice des liaisons
Variables à renvoyer
rankChaîne de caractèreschar*Classement des villes