質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

JavaScript

JavaScriptは、プログラミング言語のひとつです。ネットスケープコミュニケーションズで開発されました。 開発当初はLiveScriptと呼ばれていましたが、業務提携していたサン・マイクロシステムズが開発したJavaが脚光を浴びていたことから、JavaScriptと改名されました。 動きのあるWebページを作ることを目的に開発されたもので、主要なWebブラウザのほとんどに搭載されています。

Q&A

0回答

1491閲覧

8パズルをハッシュ表を使って最適なルートを見つける

kt3302y

総合スコア27

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

JavaScript

JavaScriptは、プログラミング言語のひとつです。ネットスケープコミュニケーションズで開発されました。 開発当初はLiveScriptと呼ばれていましたが、業務提携していたサン・マイクロシステムズが開発したJavaが脚光を浴びていたことから、JavaScriptと改名されました。 動きのあるWebページを作ることを目的に開発されたもので、主要なWebブラウザのほとんどに搭載されています。

0グッド

2クリップ

投稿2015/06/21 05:18

編集2022/01/12 10:55

javascriptのプログラムについて質問なんですが、下記のコードを参考にしてroot(hash_table,pat)関数を作成し、最適なルートを文字列で表示するプログラムを作成したいのですが、どのようにしたらよいのでしょうか。patは最適なルートを表す文字配列です。
/*

  • A hash function which outputs values
  • less than 20,011

*/
function h(pat){
var s = 0
for (var i = 0; i < 9; i++){
s = (s * 3444 + pat[i]) % 20011
}
return s
}
function eq_pat(pat1, pat2){
for (var i = 0; i < 9; i++){
if (pat1[i] != pat2[i])
return false
}
return true
}
var pat_table = []
function add_pat(pat, dist){
var v = h(pat)
if (pat_table[v] === undefined){
pat_table[v] = [[pat, dist]]
return 1
} else{
lst = pat_table[v]
for (var i = 0; i < lst.length; i++)
if (eq_pat(lst[i][0], pat)) return 0
pat_table[v].push([pat, dist])
return 1
}
}
function find_pat(pat){
var v = h(pat)
if (pat_table[v] === undefined) return -1
else {
var lst = pat_table[v]
for (var i = 0; i < lst.length; i++)
if (eq_pat(lst[i][0], pat)) return
lst[i][1]
return -1
}
}
function find_zero(pat){
for (var i = 0; i < 9; i++){
if (pat[i] == 0) return i
}
return -1
}
function work(){
var init_pat = [0, 1, 2, 3, 4, 5, 6, 7, 8]
var queue = [[init_pat, 0]]
var counter = 0
while (queue.length > 0){
var [pat, dist] = queue.shift()
var ddist = find_pat(pat)
if (ddist < 0){
add_pat(pat, dist)
counter += 1
var p = find_zero(pat)
var px = p % 3
var py = Math.floor(p / 3)
if (px > 0){
ppat = pat.slice(0)
ppat[p] = ppat[p - 1]
ppat[p - 1] = 0
queue.push([ppat, dist + 1])
}
if (px < 2){
ppat = pat.slice(0)
ppat[p] = ppat[p + 1]
ppat[p + 1] = 0
queue.push([ppat, dist + 1])
}
if (py > 0){
ppat = pat.slice(0)
ppat[p] = ppat[p - 3]
ppat[p - 3] = 0
queue.push([ppat, dist + 1])
}
if (py < 2){
ppat = pat.slice(0)
ppat[p] = ppat[p + 3]
ppat[p + 3] = 0
queue.push([ppat, dist + 1])
}
}
}
puts(counter)
}

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだ回答がついていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問