騎士の巡回問題の解の数の表示と経路表示をするには？

---

はじめまして！
千葉県の学生です。
情報を勉強してます。
騎士巡回について勉強してるのですが、解の数と経路を表示しようとすると表示できません。
どなたか教えていただけませんか？？

スタート地点は(0,0)として、経路の数と、その時間計算量を表示したいのですが＞＜

編集 削除

---

授業で紹介されたプログラムを少々改良して/**/の部分に書き加える課題なのですが、教えてください><

#include<stdio.h>
#define M 8  //板の大きさ
#define N 8  
int array[N][N];  //到達を判別
int move[M][2]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{1,-2},{2,-1}};
int n_a=0;


int main(){
   int i,j;
   for(i=0;i<N;i++){
     for(i=0;i<N;i++){
        array[i][j]=0;
        array[0][0]=1;
        try(0,0,2);  //0,0からスタート
        return 0;
     } 
   }
}

void try(int x,int y,int a_move){  //x,yからスタートする
   int n,nx,ny,i;
   long  int a,b,c;  //カウント変数
   a=0;
   b=0;
   for(i=0;i<M;i++){
     nx=x+move[i][0];
     ny=y+move[i][1];
     if(nx<0 || nx>=N) continue;  //板内にあるか判断
     if(ny<0 || ny>=N) continue;  //板内にあるか判断
     if(array[nx][ny]==0){
       array[nx][ny]=a_move;
       if(a_move==n*n){
         if(c<100000000000000) c++; 
         if(b<100000){
           c=0;
           b++;
         }
         else{
           c=0;
           b=0;
           a++;
         }
         printf(" %d    %d    %d\n",a,b,c);
       }
       else{
         try(nx,ny,a_move+1);  //バックトラック
       }
       array[nx][ny]=0;
     }
   }
}

編集 削除

---

「騎士の巡回問題」のプログラムを作るには？
https://www.petitmonte.com/bbs/answers?question_id=1862

は、いかがですか？

編集 削除

---

アルゴリズムは上のプログラムでできています！
のですが、表示の問題なのです。
解の数が桁あふれしてしまい、表示できないのでなんとかしたいのですが＞＜
多倍長整数でやろうと思うのですが、どのようにしたらよろしいでしょうか？？

編集 削除

---

for(i=0;i<N;i++){
     for(i=0;i<N;i++){

とか、
int move[M][2]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{1,-2},{2,-1}};

とか、（そもそもMは8以外になり得ないし、７つしかないよ？）

 if (a_move == n * n)
（nは一切初期化も代入もされてない）

とか、突っ込みどころ満載なんですが。
本当に
「アルゴリズムは上のプログラムでできています！」なのでしょうか？

編集 削除

---

すみません・・
できていませんでしたね・
以下のようになりました！
ところで、時間計算量はeを使って求められるようになったのですが、解の数はどれを見ればよろしいのでしょうか？
よろしくお願いします・・

#include <stdio.h>
#define M 8
#define N 5
int array[N][N];
int move[M][2] = {
  {2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1},
  {-1, -2},{1, -2}, {2, -1}
  };
long n_a = 0;
long e[5]={0,0,0,0,0};

int main(void)
{
   int i,j;
   for(i=0;i<N;i++) {
     for(j=0;j<N;j++) {
       array[i][j] = 0;
     }
   }
   array[0][0] = 1;
   try(0,0,2);
   return 0;
}

void try(int x, int y, int a_move)
{
int i, nx, ny;
   for(i=0;i<M;i++) {
     nx = x+move[i][0];
     ny = y+move[i][1];
     if(nx<0 || nx>=N) continue;
     if(ny<0 || ny>=N) continue;
     if(array[nx][ny]==0) {
       array[nx][ny] = a_move;
       if(a_move==N*N) 
         if(e[2]<(1000*1000*1000)){
           e[2]++;
           if(e[1]<(1000*1000)){
             e[2]=0;
             e[1]++;
             if(e[0]<1000){
               e[1]=0;
               e[0]++;
              }
            }
          }
          printf("%d\n",e[2]+e[1]+e[0]);  
       }
       else{
         try(nx, ny, a_move+1);
       }
       array[nx][ny] = 0;
     }
   }
}

編集 削除

---

Delphiと関係あるのでしょうか？

編集 削除

---

そもそもここはDephi Q&A掲示板ですし。

>解の数が桁あふれしてしまい、表示できないのでなんとかしたいのですが＞＜
その目的なら、1加算する操作だけあれば十分ですよね。
文字列変数を'0'で初期化しておいて、解が1つ見つかるたびに
procedure inc_num(var str: String);
var i, n: Integer;
begin
  for i := Length(str) downto 1 do
  begin
    n := Succ(Ord(str[i]));
    if n <= Ord('9') then begin str[i] := Chr(n); Exit; end
    else str[i] := '0'; // 引き続き桁上がりを処理
  end;
  str := '1' + str; // 全部0になったら1桁増やす
end;
みたいなことをすれば、メモリが許す限り何万桁でも表示できます。

FMTBcdを使っていいのであれば、TBcd型を使うと少し楽ができます。
var count: TBcd;
count := IntegerToBcd(0);
...
BcdAdd(count, IntegerToBcd(1), count);
WriteLn(BcdToStr(count));
バージョンによってはBcdAddがバグっているかもしれないので注意。
http://qc.embarcadero.com/wc/qcmain.aspx?d=20809

編集 削除

---

名前

ホームページ(ブログ、Twitterなど)のURL (省略可)

本文

←解決時は質問者本人がここをチェックしてください。

返信する