Compte tous les chemins 0-1 bord

Question

Tout d'abord désolé pour mon anglais;)

J'ai un très gros problème avec ce code. Je dois créer un "jeu". Au début, l'utilisateur a défini la taille de la carte. La carte 1xN matrice. Ensuite, il le remplit avec 0 et 1. Ensuite, l'utilisateur lance un dé. S'il obtient le nombre x (x est de 1 à 6 bien sûr), il se déplace de x cellules de gauche à droite. Si la valeur de la cellule est 0, il perd, s'il est égal à 1 - il jette à nouveau les dés. L'utilisateur gagne, s'il arrive à la bonne extrémité de la matrice, ce qui est bien sûr 1.

Nous devons compter tous les chemins possibles de gauche à droite, étiquetés 1. Quelqu'un peut-il m'aider? Voici mon code, mais ce n'est pas fini.

#include <iostream> 
#include <vector> 
#include <stdio.h> 
#include <conio.h> 
#include <math.h> 
#include <stdlib.h> 

int n,p,q; 
float a[100]; 
int T1[100]; 
int T2[100]; 
char ster; 
int i; 
typedef struct gamePathRecord { 
std::vector<int> steps; 
} gamePath; 

std::vector<gamePath> paths; 
std::vector<int> tmp; 

void countPaths(int* gameArray, int startIndex) { 
/*I tried to create funtion using vectors, but I've failed;/ 
*/ 
} 

int main(int argc, char** argv) { 

printf("How long is your board? From 6 to 100        \n"); 
scanf("%d", &n); 

if (n>100) 

printf("To big board!\n"); 
getche(); return(1); } 
if (n<6) 
printf("To small board!\n"); 

getche(); return(1); } 

printf("Give values of the cells \n"); 

printf("Number | Value\n"); 
printf("of cell |of cell\n"); 
int licznik; 
int j; 
j=0; 
for (licznik=1;licznik<n+1;licznik++) 
{ 

T1[licznik] = scanf("%d", &T1[licznik] ); 
if(T1[licznik]==1) 
    {T2[j]=licznik; 
    j++; 
    } 

//printf("%d.  %d \n", licznik, T1[licznik]); 
} 

printf("The number of possible paths wynosi: \n"); 

int k; 
for(k=1;k<n+1;k=k+1+rand()%6) //symulator kostki do gry 
{if(T1[k]==1) 
{ 
printf("Number of actuall cell %i",k," \n"); 
printf("\n"); 
printf("The value of your cell is 1!\n"); 
} 

else 
{ printf("Number of actuall cell %i",k," \n"); 
printf("\n"); 
printf("I have lost!\n"); 
break;} 
} 

getche(); 
return 0; 
} 

S'il vous plaît aider avec finlandais ce projet.

Answer 1

La question n'a pas reçu de réponse depuis un moment et je me sens un peu obligé. Mais je ne pouvais pas me résoudre à l'écrire en C++ ... au début (voir ci-dessous). La solution de base au problème est de reconnaître qu'il s'agit d'un problème de graphes/arbres (dirigé, acyclique) et de compter toutes les routes possibles pour compter, combien de fois le carré cible a été touché en effectuant une profondeur en premier recherche sur l'arbre/graphique. Depuis - dans les commentaires à la question - il a été mentionné que bien que C++ soit parfaitement capable d'implémenter la solution, ce n'est peut-être pas la langue la plus facile à choisir. Surtout pour un mathématicien, tel que l'auteur de la question, des langages plus élevés pourraient être plus intuitifs.

Que cette théorie, ou non, je laisse à personne de juger eux-mêmes;)

Voici ma solution F # au problème:

// Helper function. It lists the possible jumps from a position i0. 
// d = distance list, as computed from board with distances board 
let options_from d i0 = 
    let rec advance p s result = 
     if (i0 + p) < Array.length d 
     then 
      let x = s + (d.[i0+p]) 
      if x <= 6 
      then 
       advance (p+1) x ((i0 + p) :: result) 
      else 
       result 
     else 
      result 
    advance 1 0 [] 

// Converts the [| 0|1... |] board representation into a distance list. 
// Yields the distances to the next 1 in the board. 
let distances board = 
    board 
    |> Array.fold (fun (c,l) (x) -> 
      if x = 1 
      then 
       1,c :: l 
      else 
       c+1, l 
     ) (1,[]) 
    |> fun s -> Array.ofList (List.rev (snd s)) 


// Counts all paths in the depth first search which end on the target index. 
let count board = 
    let d = distances board 
    let end_index = Array.length d - 1 
    let rec depth_first_search i = 
     match i with 
     | _ when i = end_index -> 
      1 // Each time a path ends on end_index, we found an additional path. 
     | _ -> 
      // Count all paths to end_index from here. 
      options_from d i 
      |> List.fold (fun x i1 -> 
        x + depth_first_search i1 
       ) 0 
    (depth_first_search -1) 

let b1 = [| 1;1;1 |] 
let b1_paths = count b1 

(* 
    val b1 : int [] = [|1; 1; 1|] 
    val b1_paths : int = 4 
*) 

let b0 = [| 0;0;1;0;0;1;1;0;0;0;0;0;1; |] 
let d = distances b0 

(* 
    This is how a distance list of b0 looks like: 

    val d : int [] = [|3; 3; 1; 6|] 
*) 

// Test if options_from does what we expect it to do. 
let om1 = options_from d -1 
let o0 = options_from d 0 
let o1 = options_from d 1 
let o2 = options_from d 2 
let o3 = options_from d 3 

// compute number of paths for board b0 
let b0_paths = count b0 
(* 
    val b0_paths : int = 3 
*) 
// What will the implementation do if the last entry in board is not a 1? 
let b2 = [| 1;1;0 |] 
let b2_paths = count b2 

(* 
    Obviously this implementation does not care...Hm... 

    val b2 : int [] = [|1; 1; 0|] 
    val b2_paths : int = 2 

*) 

Avoir la solution dans la langue de haut niveau, il est pas trop difficile de trouver une implémentation en C++ (moderne) aussi. Les fonctionnalités C++ 11 pour l'itération sont pratiques pour garder le code concis. Voici la "traduction" presque directe du code F # ci-dessus en C++.

#include <cstdint> 
#include <iostream> 
#include <string> 
#include <exception> 
#include <vector> 

typedef std::vector<char> Board_t; 

typedef std::vector<int16_t> DistanceList_t; 

Board_t ReadNext(std::istream& is) 
{ 
    Board_t result; 
    std::string input; 
    is >> input; 
    for (auto c : input) 
    { 
     switch (c) 
     { 
     case '0': result.push_back(0); break; 
     case '1': result.push_back(1); break; 
     default: 
      throw std::exception("Valid input is a string of '0'|'1'. Found something else."); 
     } 
    } 
    return result; 
} 

DistanceList_t BoardToDistanceList(const Board_t& board) 
{ 
    DistanceList_t result; 
    DistanceList_t::value_type d = 1; 
    for (auto field : board) 
    { 
     switch (field) 
     { 
     case 1: 
      result.push_back(d); 
      d = 1; 
      break; 
     default: 
      d++; 
      break; 
     } 
    } 
    return result; 
} 

std::vector<int32_t> OptionsFrom(const DistanceList_t& d, int32_t i0) 
{ 
    std::vector<int32_t> result; 
    int32_t x = 0; 
    for (auto p = 1; (i0 + p) < d.size();p++) 
    { 
     x = x + d[i0 + p]; 
     if (x <= 6) 
     { 
      result.push_back(i0 + p); 
     } 
     else 
     { 
      break; 
     } 
    } 
    return result; 
} 

size_t DepthFirstSearch(const DistanceList_t& d, int32_t i) 
{ 
    if (i == d.size() - 1) 
    { 
     return 1; 
    } 
    else 
    { 
     auto move_options = OptionsFrom(d, i); 
     size_t count = 0; 
     for (auto move : move_options) 
     { 
      count += DepthFirstSearch(d, move); 
     } 
     return count; 
    } 
} 

size_t CountPaths(const Board_t& board) 
{ 
    auto d = BoardToDistanceList(board); 
    return DepthFirstSearch(d, -1); 
} 

int main() 
{ 
    bool running = true; 
    while (running) 
    { 
     try 
     { 
      auto board = ReadNext(std::cin); 
      if (board.size() > 0) 
      { 
       std::cout << "# of paths = " << CountPaths(board) << std::endl; 
      } 
      else 
      { 
       running = false; 
      } 
     } 
     catch (std::exception&ex) 
     { 
      std::cerr << "Exception: " << ex.what() << std::endl; 
      running = false; 
     } 
    } 
    std::cout << "We are done here - have a nice day." << std::endl; 
    return 0; 
}