第1回　「＋1」だけで四則演算をするには？

鹿野恵祐
2007/9/20

プログラミングの基礎となる考え方、アルゴリズムを理解しているだろうか？ ITエンジニアに贈る、アルゴリズム入門。

■京都の効率的な回り方を考えるのも「アルゴリズム」

　「アルゴリズムって何？」。そう聞かれて、皆さんはすぐに答えられますか。ウィキペディアのアルゴリズムの項には、「なんらかの問題を解くための手順のことである」と記載されています（2007年9月時点）。

　例えば、皆さんが週末に京都に旅行し、市内を観光するとしましょう。二条城や銀閣寺、東寺など、回りたいと思う観光地がいくつもあります。バスや電車、場合によっては徒歩など複数の交通手段のうち、どれを使ってどういう順番で回れば効率が良いかと考え、時刻表と格闘することになるでしょう。

　この場合、観光地の効率の良い回り方が「問題」で、すべての観光地を最短時間で移動する経路を見つけ、効率良く回る手順を考えることが「問題を解くための手順」、すなわちアルゴリズムになります。

　同じ問題でも解き方によって、解くまでにかかる時間が変わってきます。やり方によっては、100倍・1000倍の速度の違いが出てきます。この1000倍の差をハードウェアで吸収しようとすると、1000台のPCがあっても実現できないでしょう。やり方を考えるだけでそんなにも早く解けるなんて、面白いと思いませんか？

　この連載では3回にわたって、皆さんに身近な問題からアルゴリズムに触れてもらいたいと思います。

■ばらばらになったトランプをきれいに並べ直す

　皆さんがコンピュータに何かの処理をさせたいと思ったら、そのためのプログラムを書くことになりますね。でも、実際にプログラムを書く前に、まずどういったフローで処理させるかを考えると思います。

　100個の数字を小さい順に並べたければ、ソートをしようと思うでしょう。環境によっては、コンピュータ言語がすでに並べ替えのための仕組みを持っていることがありますね。SQLであれば「order by」、CやJavaであればソート用の関数やAPIが使用できるでしょう。しかし、そういった言語の支援が受けられない場合はどうすればいいでしょうか。自分で並べ替えの方法を考えて、プログラムを書く必要があります。

　例えば、遊び終わったトランプを並べ替えることを考えてみましょう。スペードのエースを先頭に、スペードの2、3と続いてキングまで、次にダイヤのエースからキングまで、クラブのエースからキングまで……というようにきれいに並べてしまっておこうと思ったら、どうやって整理しますか。52枚のカード（ジョーカーを除く）の山からスペードのエースを探して抜き出し、次にスペードの2のカードを抜き出し……という方法もありますし、7並べのようにあらかじめ各カードを置く場所を決めておき、そこにカードを当てはめていくといった方法もありますね（図1）。

図1　トランプをある順番に並べ替える

　これがトランプの並べ替えのアルゴリズムです。いま挙げた2つ以外にも方法はあるでしょうが、この2つの方法だけ見ても、並べ替えにかかる手間（時間）と必要なスペース（メモリ）は違うはずです。イメージはできましたでしょうか？

■＋1しかできないコンピュータ

　実際のアルゴリズムについて考えてみましょう。ここでは加減乗除を例として挙げます。

　四則演算ができないちょっと変わったコンピュータがあったとします。でもこのコンピュータは、ある数値に＋1をすることはできます。このコンピュータで2つの数字を加減乗除させる必要が出てきた場合、どういう処理をさせますか？

　足し算をさせようと思ったら……。例として「5＋3」を考えてみましょう。最初の5を読み込み、これに＋3をするためには、＋1を3回繰り返せばいいですね。

　次に引き算です。「5−3」は、−3に＋1することを5回繰り返せばいいのです。

　掛け算と割り算は、それぞれ足し算・引き算を繰り返すと考えます。掛け算は足し算のアルゴリズムを使って、5を3回足し合わせます。割り算は、同様に引き算のアルゴリズムを使って、5から3を何回引けるかと考えます。

　というわけで、＋1という処理ができれば、四則演算は可能であるということが分かりました。

　以下は、このアルゴリズムをC言語とJavaで表したものです。

C言語（ソースファイルのダウンロードもできます）

#include <stdio.h> int add(); int sub(); int multi(); int div(); void main(){         int a,b,c,ans=0;         printf("1以上の自然数を2つ入力してください\n");         scanf("%d %d",&a,&b);         if(a < 1 || b < 1) {                 printf("1より小さい数が入力されています\n");                 return;                 }         printf("何をしますか？(1:＋,2;−,3:×,4;÷)：\n");         scanf("%d",&c);         switch (c){                 case 1: ans = add(a,b);                         break;                 case 2: ans = sub(a,b);                         break;                 case 3: ans = multi(a,b);                         break;                 case 4: ans = div(a,b);                         break;                 default: break;         }         printf("答えは %d です。",ans); } int sub(int a,int b){         int ans = 0;         ans = add(-b,a);         return(ans); } int multi(int a,int b){         int count,ans = 0;         for(count=0;count<b;count++){                 ans = add(ans,a);         }         return(ans); } int div(int a,int b){         int ans = 0;         while(a>=b){                 a = sub(a,b);                 ans++;                 }         return(ans); } int add(int a,int b){         int count,ans = a;         for(count=0;count<b;count++){                 ans++;         }         return(ans); }

Java（ソースファイルのダウンロードもできます）

import java.io.*; public class enzan{         public static void main(String[] args)throws Exception{                 int a,b,ans=0;                 BufferedReader str = new BufferedReader(new InputStreamReader(System.in), 1);                 System.out.println("1以上の自然数を1つ入力してください");                 a = Integer.parseInt(str.readLine());                 System.out.println("1以上の自然数をもう1つ入力してください");                 b = Integer.parseInt(str.readLine());                 if(a<1 || b <1){                         System.out.println("1より小さい数が入力されています。");                         System.exit(1);                 }                 System.out.println("何をしますか？(1:＋,2:−,3:×,4:÷)：");                 int c = Integer.parseInt(str.readLine());                 switch (c){                 case 1:                         ans = add(a,b);                         break;                 case 2:                         ans = sub(a,b);                         break;                 case 3:                         ans = multi(a,b);                         break;                 case 4:                         ans = div(a,b);                         break;                 default: break;                 }                 System.out.println(ans);         }         public static int div(int a,int b){                 int ans = 0;                 while (a>=b){                         a = sub(a,b);                         ans++;                 }                 return(ans);         }         public static int multi(int a,int b){                 int count,ans = 0;                 for(count=0;count<b;count++){                         ans = add(ans,a);                 }                 return(ans);         }         public static int sub (int a,int b){                 int ans = 0;                 ans = add(-b,a);                 return(ans);         }         public static int add (int a,int b){                 int count,ans = a;                 for(count=0;count<b;count++){                         ans++;                 }                 return (ans);         } }

64ビットでも表せない、巨大な数字を扱いたい！ そんなときには？

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）