騎士の巡回問題の解の数の表示と経路表示をするには？
はじめまして！
千葉県の学生です。
情報を勉強してます。
騎士巡回について勉強してるのですが、解の数と経路を表示しようとすると表示できません。
どなたか教えていただけませんか？？
スタート地点は(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
| ツイート |  |