2004-08-21
「123456789」は数字をどう並び替えても３で割り切れる
というトリビアが紹介されていました。
放送の内容は次のようなものでした。
日本数学検定協会の東原正二郎さんはこう語る。
東原：確かに「123456789」は各位の数字をどう並び替えても３で割り切れます。実際にやってみた
123456789÷3 = 41152263 割り切れた
145236789÷3 = 48412263 割り切れた
235198764÷3 = 78399588 割り切れた
542193768÷3 = 180731256 割り切れた
…
Ｑ：並び替えると何通りある？
東原：36万2880通りあります。実際に36万2880通り
やってみない
気になる方は ご自分でお試し下さい(補足トリビア)
整数には、各位の和が 3の倍数になれば 3で割り切れるという性質がある。 今回の 123456789 の場合、各位の和は 1+2+3+4+5+6+7+8+9 = 45 で 45 は 3の倍数であるため 123456789 をどう並び替えても 3で割り切れるということになる。
数学的な証明は行なわれず、幾つか試して諦めたという感じ。 まぁ、カードを手で並べ換えて電卓で計算する方法では限界があるし、人為的ミスも入り込みます。 何より映像として面白くなさそう。 内容的にはダメでも、番組的にはOKなのかも知れません。1
「気になる方は ご自分でお試し下さい」との事なので、ひとつ試してみるかなと。
せっかくだから、綾織（PersonaWare2002, Chararina 向け）を使って。
ポイントは 1〜9 の数字を１つづつ使って 9桁の整数を生成する所でしょう。 重複なく，漏れないように、そして高速に。 更に言えば、開発期間が短くデバッグやメンテナンスが楽なように。 これらの要求をどの程度満足しているかは分かりませんが、とりあえず思い付いた方法を下記に紹介します。 安易な方法ですが、すぐ思い付く分、単純で分かり易いという事にしておきましょう（←むりやり正当化）。
番組でも使われた、数字を書いた９枚のカードに例えるのが分かり易いでしょう。 カードを一列に並べ、端から順に取るカードを選択します。 選択したカードを取ることができれば、次のカードを選択します。 重複するカードを選択していたら、エラーとしてその試みを破棄します。 エラーなく 9枚のカードを取れたら取った順に上桁から並べ、3で割り切れることを確認します。
まず、人間だったらどうやるかを考えてみましょう。
端から順に [1],[2],[3],… ,[9] を取る処理を繰り返す事にします。 最初は [1]、次に１枚目を取る時は [2]、という具合。 どうせ全ての組合せを試すのですから、ランダムに取っていくメリットはありません。
取ったカードには、「取ったよ」という意味で印を付けます。 ここでは"使用済"フラグと呼ぶ事にします。 以後、このカードを「戻す」まで（次の組合せを試みるまで）は、使用済のカードを選択しても取ることはできません。 取ったカードは覚えておいて、次回に１枚目のカードを選ぶときに自分同士で重複させないようにします。
続いて、２枚目のカードを取る処理を行ないます。
全ての組合せを試すので、何も考えず端から [1],[2],[3],…,[9] を選ぶ処理の繰り返しになります。 ただし、既に１枚取っていますので、選んだカードが使用済になっているかもしれません。 選ぶことは常にできますが、取れるかどうかは分かりません。
選んだカードが"使用済"だった場合、どうしましょうか？ 既に取られているカードをもう一度取ろうとしているのですから、不当な組合せです。 エラーですので、３枚目以降を取る意味がありません。 よって、３枚目以降を取る（無駄な）処理はスキップして、さっさと別の（２枚目の）カードを選び直すことにします。
使用済でなければ、選んだカードを取りそのカードを使用済にします。 どのカードを取ったかは覚えておきます。
続いて３枚目のカードを取る処理を行ないます。
これまでと同様に、端から [1],[2],[3],…,[9] を順に選んで、選んだカードが使用済の場合はエラーとして除外し、次の（３枚目の）カードを選択し直します。
選んだカードが使用済でなければ３枚目として取ることができます。
何か気付きますね？ そう、２枚目を取る処理と同じです。 違いは、使用済の印が付いたカードの枚数だけです。 その意味で１枚目を取る処理も「使用済のカードが 0枚」と見る事ができ、何枚目のカードを取る処理も中身は同じと言うことです。 つまり、同じ処理を９桁分繰り返せばよいという事になります。
無事に 9枚のカードを取り終えたら、生成された９桁の整数が３で割り切れるかどうかの判定を行ないます。 3 で割った余り（剰余）が 0 か否かで判断するのが普通でしょうか。 綾織では、剰余を求める演算子 % が用意されていますから、これを使えばよいでしょう。
その後は？ とりあえず、最後に取ったカードを戻しましょうか。 この時、使用済フラグもいっしょに解放します。 この後はエラー（重複したカードを取ろうとした）時の対応と同じで、N枚目のカードを戻したら N枚目の別のカードを取るべく試みます。
もう取るべきカードが無ければ、さらに１枚、(N-1)枚目のカードを戻します。 そして同様に、(N-1)枚目のカードを選び直します。 この後は、また９桁の数を作るべくカードを取っていきます。
１枚目のカードを戻し、次に取るべき１枚目のカードが無くなったところで、全組み合わせの走査が終了します。
考えたアルゴリズムを、綾織言語で実装できるように、処理を考えてみます。
まずは N枚目のカードを選ぶために、1〜9 を走査するループが必要です。 以下の処理全体がこのループの中で繰り返し処理されます。
カードを選んだら、まず選んだカードが使用済みか否かを判断します。
使用済みの場合は、そのカードは取れないのでした。 以降のカードを取る処理はスキップして、次の N枚目のカードを選択します。 これはつまり、何もしないで走査ループを継続するという事です。
まだ取られていない場合は、そのカードを取ります。 当該カードに"使用済"の印をつけます。
カードが取れたら、次のカードを取ります。 ですが、唯一次のカードを取らない条件がありました。 言うまでもなく、９枚目を取った後です。 したがって、N枚目のカードが９枚目かどうかを判断する必要があります。
取ったカードが１枚目〜８枚目の時、次のカードを取ります。
取ったカードが９枚目の時、３で割り切れるかどうかの判断を行います。
以上の手順をフローチャートにすると、次のような感じになります。
ちょっと綾織言語風に書いてみましょうか：
// N枚目のカードを取る処理
for( i=0; i<9; i++ ) {
if( 使用済 ) {
何もしない;
} else {
カードを１枚取る;
使用済み設定;
if( 最後の桁 ) {
３で割り切れる？;
} else {
次のカードを取る;
}
}
}
フローチャートの中に、[次のカードを取る]処理がありますね。 例えば、２枚目→３枚目のとき、３枚目のカードを取る処理がこれに当たります。 ２枚目の処理と３枚目の処理は同じですから、ここにはフローチャートの処理全体がそっくりそのまま入ります。
//……………………………………………………
// N枚目のカードを取る処理
for( i=0; i<9; i++ ) {
if( 使用済 ) {
何もしない;
} else {
カードを１枚取る;
使用済み設定;
if( 最後の桁 ) {
３で割り切れる？;
} else {
次のカードを取る;
//……………………………………………………
// N+1枚目のカードを取る処理
for( i2=0; i2<9; i2++ ) {
if( 使用済 ) {
何もしない;
} else {
カードを１枚取る;
使用済み設定;
if( 最後の桁 ) {
３で割り切れる？;
} else {
次のカードを取る;
//……………………………………………………
// N+1+1枚目のカードを取る処理
for( i3=0; i3<9; i3++ ) {
(以下省略)
}
//……………………………………………………
}
}
}
//……………………………………………………
}
}
}
//……………………………………………………
この様な感じで、中に入ったフローチャートの [次のカードを取る] の中にも、そっくり同じフローチャートが入ります。
例えばひとつの関数でこれを処理する時、for ループのループカウンタは別々に９つ用意する必要があります。
その部分だけを書き出すと、次のような感じになるでしょう。
選択するのはカードが取れる/取れないとは無関係ですから、111111111〜999999999 の全組み合わせを試みます。 この時、各桁は他の桁が何であるかとは無関係に [1]〜[9] を取り得ます。 正直に組み合わせると各桁が [1]〜[9] の９通り、全９桁なので、9×9×9×9×9×9×9×9×9 = 3億8742万0489 通りですね。 各桁の値を個別に管理する必要があり、具体的には変数も９つ必要になります。
for( i1=0; i1<9; i1++ ) { // １枚目
for( i2=0; i2<9; i2++ ) { // ２枚目
for( i3=0; i3<9; i3++ ) { // ３枚目
for( i4=0; i4<9; i4++ ) { // ４枚目
for( i5=0; i5<9; i5++ ) { // ５枚目
for( i6=0; i6<9; i6++ ) { // ６枚目
for( i7=0; i7<9; i7++ ) { // ７枚目
for( i8=0; i8<9; i8++ ) { // ８枚目
for( i9=0; i9<9; i9++ ) { // ９枚目
}
}
}
}
}
}
}
}
}
上記のとおり、for の中身は「N枚目のカードを取る」処理で、その中の [次のカードを取る]処理が子の for なわけです。
現実には上記の "綾織風"フローチャートの [次のカードを取る] の所に同じフローをもう１セット書き、更にその中にもう１セット書き… を繰り返すわけで。
ちょっとやってられません。
同じことは、"使用済"フラグにも言えます。 "使用済"フラグは文字通り使用済みを表すだけなので、どんな順番で"使用済"になったかは分かりません。 なので、「１枚戻す」事ができません。 戻すためには、ループ毎に、下位ループから戻った時の"使用済"状態を覚えておくのが楽です。 つまり、状態を覚えておく変数を９つ用意する必要があります。
ここまで触れていませんでしたが、実は「取ったカード」もどんな順番で取ったかは記録されていませんので同じことが言えます。
「同じ処理」という物は、サブルーチン（関数）にまとめて再利用できるようにするのが基本です。 その方が把握すべき処理の分量が減りますし、問題があったとしても１箇所修正すればよいので修正モレを防ぐ事にもなります。 なので、上記フローチャートも、ひとつの関数として実装するのが好ましいでしょう。 "カードを取る"関数とでもしておきましょうか。
そこで [次のカードを取る]処理ですが、手近にいい関数があるじゃないですか。 そう、[カードを取る]処理から、自分自身である[カードを取る]処理を呼び出せばいいのです。 この様な処理を、再帰呼出し（recursive call）と言います。 再帰呼出しではスタックの使用量に気を配る必要がありますが、今回は大した事なさそうなので大丈夫でしょう。2
上記のとおり「N枚目の処理」や「使用済フラグ」はループの階層毎に覚えておく必要がありました。 ついでに「取ったカード」の履歴も階層毎に覚えておくのがよいでしょう。 これを引数として渡す事にします。 覚えておくべき階層を「ループ毎」から「関数毎」に置き換えてやるわけです。
カードを取る( N枚目, 取ったカードの履歴, 使用済フラグ )
{
for( i=0; i<9; i++ ) {
if( 使用済 ) {
何もしない;
} else {
カードを１枚取る;
使用済み設定;
if( 最後の桁 ) {
３で割り切れる？;
} else {
カードを取る( N+1枚目, 取ったカードの履歴, 使用済フラグ );
}
}
}
}
だいぶ綾織のプログラムらしくなって来ました。
処理の中身が決まれば、あとは日本語で書かれている処理を実際の綾織コードに直していくだけです。 ちょっとアレですが、まぁこんな感じって事で。
なお、下記のコードでは、途中経過をフキダシに表示します。 実際にやってみれば分かりますが、非常に遅いです。 恐らく何時間も掛かる上にその間はリソースを大量消費しますので、他のキャラクターや他のタスクの動作に支障があります。 実際に試すには、途中経過をログファイルに書き出すようにして、画面表示は最小限に留める必要があるでしょう。
//----------------------------------------------------------
// 123456789を並べ換えて９桁の数字を生成
//----------------------------------------------------------
// in int iColId = 何枚目のカードを取る処理かを指定
// int iNumCurr = ここまで取ったカードで作った数
// boolean bUseFlagCurr[9] = ここまで取った使用済フラグ
// out なし
//----------------------------------------------------------
void vfCreateNum( int iColId, int iNumCurr, boolean bUseFlagCurr[9] )
{
int i;
int j;
int iNumNext;
boolean bUseFlagNext[9];
for( i=0; i<9; i++ ) {
if( bUseFlagCurr[i] ) {
// 使用済3
} else {
// 未使用
iNumNext = iNumCurr * 10 + INumTbl[i];
if( iColId < 8 ) {
// 途中の桁
for( j=0; j<9; j++ ) {
bUseFlagNext[j] = bUseFlagCurr[j];
}
bUseFlagNext[i] = true;
vfCreateNum( iColId+1, iNumNext, bUseFlagNext );
} else {
// 最下位の桁
vfCheckNum( iNumNext );
}
}
}
}
//----------------------------------------------------------
// ３で割りきれるか確認
//----------------------------------------------------------
// in int iNumTgt = 評価対象の値
// out なし
//----------------------------------------------------------
void vfCheckNum( int iNumTgt )
{
string sProgress;
sProgress = itoa(IDataCountOK+IDataCountNG+1) + ": "
+ itoa(iNumTgt) + "÷3 = " + itoa(iNumTgt/3) + " … ";
if( (iNumTgt % 3) == 0 ) {
sProgress = sProgress + "割り切れた。\n";
IDataCountOK++;
} else {
sProgress = sProgress + "割り切れない。\n";
IDataCountNG++;
}
// 結果を話す
Talk( sProgress );
}
int INumTbl[9]; // 数字のカード int IDataCountOK; // ３で割りきれた件数 int IDataCountNG; // ３で割りきれなかった件数
void vfCreateNum( int iColId, int iNumCurr, boolean bUseFlagCurr[9] ); void vfCheckNum( int iNumTgt );
void main( )
{
int r;
int iTimeStart;
int iTimeEnd;
int iTimeDiff;
int iH;
int iM;
int iS;
boolean bUseFlag[9];
for( r=0; r<9; r++ ) {
bUseFlag[r] = false;
}
Talk( "「『123456789』は数字をどう並び替えても３で割り切れる」を、試してみます。\c" );
iTimeStart = Time();
SetTalkWaitMode( 1 ); // set NoWait mode
IDataCountOK = 0; // カウンタ初期化
IDataCountNG = 0;
for( r=0; r<9; r++ ) { // 数字テーブル初期化
INumTbl[r] = r + 1;
}
vfCreateNum( 0, 0, bUseFlag ); // 検証開始
SetTalkWaitMode( 0 ); // set Normal mode
iTimeEnd = Time();
iTimeDiff = iTimeEnd - iTimeStart;
iH = iTimeDiff / 3600;
iM = (iTimeDiff % 3600) / 60;
iS = (iTimeDiff % 3600) % 60;
Talk( "確認時間 = " + itoa(iH) + "時間" + itoa(iM) + "分" + itoa(iS) + "秒\n" );
Talk( "組合せ総数 = " + itoa( IDataCountOK + IDataCountNG ) + "\n" );
Talk( "割り切れた = " + itoa( IDataCountOK ) + "\n" );
Talk( "割り切れない = " + itoa( IDataCountNG ) + "\n" );
Talk( "\n" );
if( IDataCountNG == 0 ) {
Talk( "確かに「123456789」は数字をどう並び替えても３で割り切れた。\p" );
} else {
Talk( "なんか変だよ？\p" );
}
}