Zählen Sie alle Pfade 0-1 Board

Question

Vor allem Entschuldigung für mein Englisch;)

Ich habe ein wirklich großes Problem mit diesem Code. Ich muss ein "Spiel" erstellen. Zu Beginn hat der Benutzer die Größe des Boards eingestellt. Die Platine 1xN Matrix. Dann füllt er es mit 0 und 1. Als nächstes wirft der Benutzer einen Würfel. Wenn er die Zahl x bekommt (x ist natürlich 1 bis 6), bewegt er sich von x-Zellen von links nach rechts. Wenn der Wert der Zelle 0 ist, verliert er, wenn er gleich 1 ist, erneut. User gewinnt, wenn er an das rechte Ende der Matrix kommt, was natürlich 1 ist.

Wir müssen alle möglichen Wege von links nach rechts mit der Bezeichnung 1 zählen. Kann mir jemand helfen? Hier ist mein Code, aber es ist nicht fertig.

#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; 
} 

Bitte helfen Sie mit Finnisch dieses Projekt.

Answer 1

Die Frage ist seit einiger Zeit nicht beantwortet und ich fühle mich irgendwie verpflichtet. Aber ich konnte mich nicht dazu bringen, es in C++ zu schreiben ... zuerst (siehe unten). Die grundlegende Lösung des Problems besteht darin, zu erkennen, dass es sich um ein (gerichtetes, azyklisches) Graph/Baum-Problem handelt und das Zählen aller möglichen Routen zählt, wie oft das Zielquadrat beim Ausführen einer Tiefe zuerst getroffen wurde Suche im Baum/Diagramm.

Da - in den Kommentaren zu der Frage - es wurde erwähnt, dass, während C++ perfekt in der Lage ist, die Lösung zu implementieren, es möglicherweise nicht die einfachste Sprache zu wählen ist. Besonders für einen Mathematiker, wie den Autor der Frage, könnten höhere Sprachen intuitiver sein.

Ob diese Theorie hält oder nicht, lasse ich selbst jemanden zu beurteilen;)

Hier meine F # Lösung für das Problem:

// 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 

*) 

die Lösung in der Hochsprache zu haben, ist es nicht allzu schwierig, auch in (modernem) C++ eine Implementierung zu finden. Die C++ 11-Funktionen für die Iteration sind praktisch, um den Code übersichtlich zu halten. Hier die fast direkte "Übersetzung" des obigen F # -Codes nach 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; 
}