バックトラック法について
■ このスレッドは過去ログ倉庫に格納されています
0001777
NGNG問題は、A,B,C,D,E,F,G,Hという８つの町があり、それぞれにA-Bは11分1111円、A-Bは22分2222円…という問題です。この問題の最短時間でいけるプログラムと、最も低額でいけるプログラムを作る問題です。
正直、まったくもってわかりません。これの答えとしてパスカル言語はあるのですが、これをC言語に直すこともできません。せめて、このパスカル言語さえC言語に直せれば…。
できれば皆様に、問題を解くほうでも、パスカル言語をC言語になおす方法（答え）でも,どんな些細なことでもいいの教えてください。皆様を博識と思い、お願いします。
0002777
NGNGprogram route(input,output);
const INFINITY=32767;
N=10;
type points=1...N;
var map:array[points,points] of integer;
route:array[1...N] of points;
notpassed:array[points] of boolean;
np,start,goal,i:points;
nroute,mindist,minroute:integer;
procedure readmap;
var i,j:points;
begin
readln(np);
for i:=1 to np do
begin
for j :=1 to np do red(map[i,j]);
readln
end
end;
procedure findroute(step:integer; cur:points; dist:integer);
var next:points;
0003777
NGNGvar i:points;
begin
nroute:=nroute+1;
write(nroute:3,':');
for i:=1 to step-1 do write(route[i]:1,'-');
writeln(route[step]:1,'distance='dist);
if dist<mindist then
begin
mindist:=dist;minroute:=nroute
end
end;
begin
route[step]:=cur;
notpassed[cur]:=FALSE;
if cur=goal then printroute
else
for next:=1 to np do
if(map[cur,next]>0)and notpassed[next] then
findroute(step+1,next,dist+map[cur,next]);
notpassed[cur]:=TRUE
end;
begin
readmap; readln(start,goal);
for i:=1 to np do notpassed[i]:=TRUE;
nroute:=0; mindist:=INFINITY;
findroute(1,start,0);
if nroute>0 then writeln('the shortest route is No.',minroute)
end.
0004デフォルトの名無しさん
NGNG0005デフォルトの名無しさん
NGNG0006デフォルトの名無しさん
NGNG0007デフォルトの名無しさん
NGNG00081
NGNG助けてください。
0009デフォルトの名無しさん
NGNG甘えるなよ。
0010777
NGNG0011デフォルトの名無しさん
NGNG0012デフォルトの名無しさん
NGNGprocedure の中に procedure 。
優れているというか、スコープうざいというか。
0013デフォルトの名無しさん
NGNG最小全域木の部分グラフでいいんだっけ？ 違うか。違うな。
start から一番近い点を得る。
このグラフから一番近い点を得る。
そのグラフから一番近い点を得る。
こうしていくときグラフは常に木である。
そのうちに goal が見つかれば、最短経路が見つかったことになる。
なぜならこれより短い経路が存在すれば、途中で見つかっているはずだからである。
それはなぜかというと新しく加わる点 p はそのときの部分木から一番近い点であると決めたが、
p より部分木から遠い点 q を通ってから p に至る道のほうが、直接 p に行くより近いわけはないからでありぐだぐだぐだぐだ
俺はこれで学位を取った。
0014デフォルトの名無しさん
NGNG単なるダイクストラ法の卒論でOKが通るな。
0015デフォルトの名無しさん
NGNG「般教でプロローグやった」
と言い出す厨が出現する、に8クイーン
0016デフォルトの名無しさん
NGNG0017デフォルトの名無しさん
NGNGC/C++の宿題を必殺仕事人始末人 17代目
http://pc2.2ch.net/test/read.cgi/tech/1070469896/101
しかし・・・卒論終わらんで困ってるんですって人おおいのぉ。
そんなんでお外にでて大丈夫なんかなぁ・・・。
0018デフォルトの名無しさん
NGNG伸縮するboolean-closureのコンテナの設計をちと考えてみる。
a)無向グラフ：同じ組み合わせを含める
1:1
2:1 2:2
3:1 3:2 3:3
4:1 4:2 4:3 4:4
size(n) = ((n + 1) * n / 2)
ref(x, y) = size(max(x, y) - 1) + min(x, y)
b)リーグ戦表：同じ組み合わせを排除する
2:1
3:1 3:2
4:1 4:2 4:3
size(n) = ((n + 1) * n / 2) - n
ref(x, y) = size(max(x, y) - 1) + min(x, y)
0019デフォルトの名無しさん
NGNG002018
NGNGttp://www.buzz-style.net/~capslockabc/boolean.html
0021デフォルトの名無しさん
NGNG漏れ、そこの >>105 だが、漏れが笑われているのか？
ところで、ここで一つ修正。
>if( ( z->r.score = s ) < r.score );
>r = z->r;
>if( ( z->r.score = s ) < r.score )
> r = z->r;
いつのまにか、変な ';' が入っていたみたい。
（１度ソースを書式整形ツールに廻したばかりに・・・）
0022777
NGNG0023デフォルトの名無しさん
NGNGそのｱﾌﾟﾘｹｰｼｮﾝ、ﾊﾟｿｺﾝｼｮｯﾌﾟに29800円くらいで売ってたような・・・。
002418
NGNGあんたは、WIN32バイナリをとってきたほうがヨイ。
http://www.mingw.org/download.shtml#hdr2
proposed:
bin gpc-2.1-mingw-1.exe
0025777
NGNGありがとうございます。
やっぱりスレ立てたほうが回答早いですね。
0026デフォルトの名無しさん
NGNG今晩中にかたづけないといかんのか？
0027デフォルトの名無しさん
NGNG論文の本題はグラフ理論関係のオリジナルのアプリケーションなんだけどね。
学位授与機構の試験が、この手のを「説明せよ」ってのが半分占めてたんで、
何か知識や記憶で取ってしまった感じになった。
0028デフォルトの名無しさん
NGNG糞スレ立てた上にこの言いぐさかよ。
頼むから、頼むからさ、
この世のために死んでくれ！！！！！！！
0029デフォルトの名無しさん
NGNG単発質問でスレを立てないでください。
アルゴリズムとデータ構造なら俺に聞け
http://pc2.2ch.net/test/read.cgi/tech/1025264999/
0030デフォルトの名無しさん
NGNG１はこの後どうするのだろうか？もうこのスレではまともな返事は期待できないぞ。
まぁ自業自得でしょうが。
0031デフォルトの名無しさん
NGNG「そんなのスレ立てれば誰か教えてくれるからいいです。」と考えているに一票。
0032デフォルトの名無しさん
NGNGヽ( ｀д´)ノ ume
0033デフォルトの名無しさん
NGNGヽ( ｀ д ´)ノ ume
0034デフォルトの名無しさん
NGNG0035test&rlo;tset&lro;
NGNG0036なんやの？lo;？のやんな&lro;
NGNG0037がーん lo;んーが &lro;
NGNG0038電脳プリオン
NGNG0039デフォルトの名無しさん
NGNG,..::'"´:,:'ﾞ´｀ヽ,:'ﾞ´｀ヽ｀'::､
／:::::;:､-i ^ l ^ i‐- ;ヽ,
/:::::;: '´‐-､｀'ー''(´｀)ｰ" ''ﾞ´ ヽ;',
i':::::/ , -─‐- | ﾆニ￣ }.i!
{:::::i i｀''ｰ- ､..,,,,,___|＿_,,,,..､‐iﾞ i
.i::::!. ', ______ / /
,..., .ヽ::､ ヽ,´ ｀ﾞヽ, ,／.／ ／￣￣￣￣￣￣￣
iﾞ iｰ"ﾞ'ゝ､.,,_`'‐､.,,___,,...ゝ'",.／ ＜ のび太く〜ん
｀;ー''ゝ:::::::::::,二M=w-､‐=''"´ ＼＿＿＿＿＿＿＿
／ ○/:::::::::/´ ゝソ/＼...,
'､__,..!,{::::::::::{ 「｀ﾞﾞ'''ｰ-､/`'（ ）
｀ヽ::::::::`::.,''ｰ--,／ ｀"´
(`'ｰ--‐ﾞ<"´
`'‐---‐'
0040デフォルトの名無しさん
NGNG( ´∀｀） ||＜ このスレッドはこれにて終了！
（≡Ｖ/_~つ ＼ お後がよろしいようで。
（_＿Ｙ＿_） ＼＿＿＿＿＿＿＿＿＿＿＿＿
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
Λ_Λ Λ_Λ Λ_Λ Λ_Λ ／￣￣￣￣￣￣￣
Λ_ΛΛ_ΛΛ__ΛΛ_ΛΛ_Λ＜ ＞１ オマエモナー
´∀｀( ´∀｀)´∀｀( ´∀｀)´∀｀) ＼＿＿＿＿＿＿＿
0041デフォルトの名無しさん
NGNG0042デフォルトの名無しさん
NGNG0043デフォルトの名無しさん
NGNG0044デフォルトの名無しさん
NGNGス
ト
テ
ス
ト
テ
ス
ト
0045デフォルトの名無しさん
NGNG0046デフォルトの名無しさん
NGNG0047デフォルトの名無しさん
NGNGNullPo完全
0048デフォルトの名無しさん
NGNGｶﾞｯ 完全
0049デフォルトの名無しさん
NGNG■ このスレッドは過去ログ倉庫に格納されています