まず、設定を考える。
(1,2)と書かれたとき、球番号1と球番号2が接触していることを意味しているとして、
pair(0)=(1,2)
pair(1)=(4,9)
pair(2)=(2,7)
pair(3)=(12,5)
pair(4)=(12,1)
pair(5)=(7,1)
pair(6)=(10,3)
pair(7)=(14,2)
と8つの球２つが接触しているペアが存在するとする。
これを見ると、1、2、7、12、5、14の６つの球がくっついてるとわかるであろう。
ペアが8つぐらいなら目視で判断できるけど、ペアが1000個とかになると相当きつい。
これを解決するアルゴリズムを考えて、さらにそのプログラムを組んで
４つ以上の球が接触して連なってるかの確認が一瞬でできるようにしてみよう。
まずは、ペア８つの場合、目視でどう解いたかを考える。
pair(0)に書いてある球番号1,2が他のペアにもあるか確認をする。
pair(2),pair(4),pair(7)が確認できる。
そして、pair(2),pair(4),pair(7)の中を見て
1or2の球にくっついているのは、球7と球12と球14であることがわかる。
さらに、7or12or14の球にくっついてるペアがあるか(pair(0),pair(2),pair(4),pair(7)以外で)を
確認する。
するとpair(3)で球12が球5とくっついてることがわかる。
そして、球５がくっついてるペアを(pair(0),pair(2),pair(3),pair(4),pair(7)以外で)
があるかを探す。
見つからないので終わる。
球が1,2,7,12,5,14の6つの球が接触して連なってることを確認する。
そしてpair(0),pair(2),pair(3),pair(4),pair(7)以外のペアでも４つ以上連なってないか確認する。
とこんな感じでペア８つの場合なら４つ以上の球が接触して連なってるか確認できる。
ペアが1000個の場合も同様にできると考えて、プログラムを
javascriptで書いてみた。
---------------------
スポンサードリンク
-----------------------
書いてみたのを下に表示する。
javascriptで書いてみた。
---------------------
スポンサードリンク
-----------------------
書いてみたのを下に表示する。
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="ja" lang="ja">
<head>
<title>4つ消す</title>
<script type="text/javascript">
function init_main(){
var pair=new Array();
pair[0]=[1,2];
pair[1]=[4,9];
pair[2]=[2,7];
pair[3]=[12,5];
pair[4]=[12,1];
pair[5]=[7,1];
pair[6]=[10,3];
pair[7]=[14,2];
var pair_kosuu=8;//ペアの個数
//0:まだ４つくっついてるかの確認を行ってないペア,1:確認済み
var irokakunin=new Array(pair_kosuu);
for(var ss=0; ss<pair_kosuu; ss++){
irokakunin[ss]=0;
}
for(var j=0; j<pair_kosuu; j++){
if(irokakunin[j]==0){
irokakunin[j]=1;
var irotunagari=new Array();//つながった球の番号を保存
irotunagari[0]=pair[j][0];
irotunagari[1]=pair[j][1];
var irotunagari_kosuu=2;//つながった球の数
var zouka=2;//つながった球の増加数
var irotunagari_kosuu_hozon=irotunagari_kosuu;//つながった球の数を保存
var zouka_hozon=zouka;//つながった球の増加数を保存
while(zouka!=0){
zouka=0;
for(var s=j+1; s<pair_kosuu ;s++){
if(irokakunin[s]==0){
for(tt=irotunagari_kosuu_hozon-zouka_hozon; tt<irotunagari_kosuu_hozon; tt++){
if(pair[s][0]==irotunagari[tt]){
irokakunin[s]=1;
var ts=irotunagari_kosuu_hozon-zouka_hozon;
var onaji_flag=0;//同じ
while(ts<irotunagari_kosuu&&onaji_flag==0){
if(pair[s][1]==irotunagari[ts]){
onaji_flag=1;
}else{ts=ts+1;}
}
if(ts==irotunagari_kosuu){
irotunagari[irotunagari_kosuu]=pair[s][1];
irotunagari_kosuu=irotunagari_kosuu+1;
zouka=zouka+1;
}
}
if(pair[s][1]==irotunagari[tt]){
irokakunin[s]=1
var ts=irotunagari_kosuu_hozon-zouka_hozon;
var onaji_flag=0;//同じ
while(ts<irotunagari_kosuu && onaji_flag==0){
if(pair[s][0]==irotunagari[ts]){
onaji_flag=1;
}else{ts=ts+1;}
}
if(ts==irotunagari_kosuu){
irotunagari[irotunagari_kosuu]=pair[s][0];
irotunagari_kosuu=irotunagari_kosuu+1;
zouka=zouka+1;
}
}
}
}
}
irotunagari_kosuu_hozon=irotunagari_kosuu;
zouka_hozon=zouka;
}
if(irotunagari_kosuu>=4)window.alert(irotunagari);
delete irotunagari;
}
}
}
</script>
</head>
<body>
<form name="jikken">
<input name="jikken_button" type="button" value="確認ボタン" onclick="init_main();"></br>
</form>
</body>
</html>
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="ja" lang="ja">
<head>
<title>4つ消す</title>
<script type="text/javascript">
function init_main(){
var pair=new Array();
pair[0]=[1,2];
pair[1]=[4,9];
pair[2]=[2,7];
pair[3]=[12,5];
pair[4]=[12,1];
pair[5]=[7,1];
pair[6]=[10,3];
pair[7]=[14,2];
var pair_kosuu=8;//ペアの個数
//0:まだ４つくっついてるかの確認を行ってないペア,1:確認済み
var irokakunin=new Array(pair_kosuu);
for(var ss=0; ss<pair_kosuu; ss++){
irokakunin[ss]=0;
}
for(var j=0; j<pair_kosuu; j++){
if(irokakunin[j]==0){
irokakunin[j]=1;
var irotunagari=new Array();//つながった球の番号を保存
irotunagari[0]=pair[j][0];
irotunagari[1]=pair[j][1];
var irotunagari_kosuu=2;//つながった球の数
var zouka=2;//つながった球の増加数
var irotunagari_kosuu_hozon=irotunagari_kosuu;//つながった球の数を保存
var zouka_hozon=zouka;//つながった球の増加数を保存
while(zouka!=0){
zouka=0;
for(var s=j+1; s<pair_kosuu ;s++){
if(irokakunin[s]==0){
for(tt=irotunagari_kosuu_hozon-zouka_hozon; tt<irotunagari_kosuu_hozon; tt++){
if(pair[s][0]==irotunagari[tt]){
irokakunin[s]=1;
var ts=irotunagari_kosuu_hozon-zouka_hozon;
var onaji_flag=0;//同じ
while(ts<irotunagari_kosuu&&onaji_flag==0){
if(pair[s][1]==irotunagari[ts]){
onaji_flag=1;
}else{ts=ts+1;}
}
if(ts==irotunagari_kosuu){
irotunagari[irotunagari_kosuu]=pair[s][1];
irotunagari_kosuu=irotunagari_kosuu+1;
zouka=zouka+1;
}
}
if(pair[s][1]==irotunagari[tt]){
irokakunin[s]=1
var ts=irotunagari_kosuu_hozon-zouka_hozon;
var onaji_flag=0;//同じ
while(ts<irotunagari_kosuu && onaji_flag==0){
if(pair[s][0]==irotunagari[ts]){
onaji_flag=1;
}else{ts=ts+1;}
}
if(ts==irotunagari_kosuu){
irotunagari[irotunagari_kosuu]=pair[s][0];
irotunagari_kosuu=irotunagari_kosuu+1;
zouka=zouka+1;
}
}
}
}
}
irotunagari_kosuu_hozon=irotunagari_kosuu;
zouka_hozon=zouka;
}
if(irotunagari_kosuu>=4)window.alert(irotunagari);
delete irotunagari;
}
}
}
</script>
</head>
<body>
<form name="jikken">
<input name="jikken_button" type="button" value="確認ボタン" onclick="init_main();"></br>
</form>
</body>
</html>
繰り返し処理の中に条件わけ処理、その中に繰り返し処理と
すごく複雑になっている。
このプログラムはきつい。
すごく複雑になっている。
このプログラムはきつい。
下の確認ボタンを押すと上のプログラムが起動して
４つ以上連なった球の番号を表示してくれる。
0 件のコメント:
コメントを投稿