※記法については『算数の問題文の記法のまとめ【随時更新】 - 算数の問題文の記法を考える』を読んでください。
【2000年度ジュニア算数オリンピックトライアル問題1問目】
図のように下の左(ア)にはイヌ、下の右(イ)にはネコ、上の左(ウ)にはサル、上の右(エ)にはウサギがいます。今、1回目は上と下を入れかえ(イヌとサル、ネコとウサギを入れかえる)、2回目は左と右を入れかえ、3回目は、また上と下を入れかえ、次はまた左と右を入れかえ・・・・と、次々と入れかえていきます。
20回目にはウサギはどこにいますか、(ア)~(エ)の記号で答えなさい。
【記法化】
house := [ ["Saru", "Usagi"], ["Inu", "Neko"] ]; 実行; for(i = 1;i <= 20;i++){ if(i%2 == 1){ house[0] := house[1]; house[1] := house[0]; 実行; } if(i%2 == 0){ for(i = 0; i < len(house); i++){ house[i][0] := house[i][1]; house[i][1] := house[i][0]; 実行; } } } print(house);
【工夫】
house := [ ["Saru", "Usagi"], ["Inu", "Neko"] ]; shuffle_count := 20; 実行; shuffle_count := shuffle_count % 4; 実行; for(i = 1;i <= shuffle_count;i++){ if(i%2 == 1){ house[0] := house[1]; house[1] := house[0]; 実行; } if(i%2 == 0){ for(i = 0; i < len(house); i++){ house[i][0] := house[i][1]; house[i][1] := house[i][0]; 実行; } } } print(house);
この解決策は微妙だ。4回で最初に戻ることを人間側が分析して、その余り分つまり0回実行した。分類としては画像圧縮の仕組みに近いと思う。
人間側の判断すらどうにか自動化できないだろうかとは思うが、houseが最初の状態に戻るまでをカウントしても、シャッフルの過程が同じ振る舞いでなければこのように省略できない。いやシャッフルの過程が同じ振る舞いでも場合によっては省略できないかもしれない。何にせよケースバイケースで、人間の判断が入り込んでいる。
算数の問題がプログラミングの計算量圧縮のアイデアの源泉になり得るんじゃないかとは思っているが、同じような問題が集まってこなければ何とも言えない。