課題1.4

問題

  1. m桁の整数 n について、nが３の倍数であるかどうかを判定するアルゴリズム（方法、手順）を考えて、プログラミングしなさい。入力は、m桁の10進数(場合によっては文字列)とする。

  2. あなたの考えたプログラムは、nが大きくなるにつれて、どのように実行時間が増加するだろうか。以下の3つから選び、理由を説明しよう。

    1. nの大小の関係なく、実行時間は一定、とみなしてよい。
    2. nが大きくなるにつれて、おおよそ、nの大きさに比例して増加する、と考えてよい（実際はコンピュータの処理速度が速すぎて、相当大きなnで比較しないと、そんなに差がつかない）
    3. nが大きくなるについて、おおよそ、log (n)に 比例して増加する、と考えてよい

実行例 (nと、nが3の倍数かどうかの判定だけでよい)

n ? 32451 
3の倍数です

[以下は、参考プログラムの実行例です]
n = 32451  ←　 intとして読み込まず、文字列として受け取って、いろいろ操作
m桁 : 5        文字列の長さが、桁数
3              先頭の数3
2
4
5
1              最後の数1
[ここまで：intとして読み込んで、桁数を求める方法もある]

コメント

同じ問題に、異なるアルゴリズム（手順、解法）があります。たとえば下の3つは代表例。

  1. nを3で割った剰余を利用するアルゴリズム
  2. nから3をひたすら引き続けて更新する。nが2以下になったところで、判定。
  3. 各桁を足し算した結果が3の倍数かどうかを判定する

あなたのアルゴリズムの処理時間は、nが大きくなるにしたがって、どのように増加していくだろう

  • 2n, log 10n どちらに近いだろう。
  • nの大きさに関わりなく、一定だろうか。
1 10 100
2n 2 20 200
log 10n 0 1 2
(log記法は、底を10とするとき、log 1 = 0, log 10 = 1, log 100 = 2などとなる)
  • いろいろな基本関数の増加の仕方をみておこう。 （プログラミング入門教材 AtCoder Programming Guide for beginners (APG4b)より 計算量のグラフ）

解答例

[参考、関連プログラム] [解答例] 

#include <stdio.h>
#include <stdlib.h>   /* 「スタンダード リブ」 */
#include <string.h>   /* 「ストリング　ドット　エイチ」 */

int main(void) {
    char s[100];  /* 入力文字列 */
    int n;        /* 整数 */
    int m;        /* 桁数 */

    int i;        /* 配列のインデックス */
    int d;        /* 1文字数を、1桁の整数へ */

    /* ↓の操作を参考にしながら、作成してください */

    printf("n ? ");
    scanf("%s", s);  /* 文字列として入力を */

    n = atoi(s);     /* 文字列を10進数整数へ変換 アスキーto i 「エートゥアイ」*/
    m = strlen(s);   /* 文字列の長さを求める関数0501を、組み込み関数で 桁数 */
                     /* 「エスティアール レン　あるいはストリングレン」*/

    printf("\nn = %d\n", n);
    printf("m桁 : %d\n", m);

    i = 0; 
    while (s[i] != '\0') { /* 文字列操作定番 0501 */ /* 「エス 角カッコ アイ」 */
        d = s[i] - 48;   /* アスキーコード48は '0' 1文字。アスキーコードから1桁の整数値を求める */
        printf ("%d\n", d);
        i++;
    }

     


    return 0;
}



アルゴリズム1 (3で割った余り；実行時間は一定) 
#include <stdio.h> 

int main(void) { 
    int n; 
    
    printf("n ? "); 
    scanf("%d", &n); 
    if (n%3 == 0) 
        printf("3の倍数です\n"); 
    else 
        printf("3の倍数ではありません\n"); 

    return 0; 
} 

アルゴリズム2(3未満になるまで3を引き続けて、0になったか調べる作戦) 
#include <stdio.h> 

int main(void) { 
    int n; 

    printf("n ? "); 
    scanf("%d", &n); 

    while (n => 3) { /* 3未満になるまで繰り返し3を引いていきます */ 
        n -= 3;
    } 

    if (n == 0) 
        printf("3の倍数です\n"); 
    else 
        printf("3の倍数ではありません\n"); 

    return 0;
} 
nが大きくなると、whileループ数がnに比例して増加します。
 n=100、n= 200, n=10000, n=20000 をイメージしてみるとよい。 
（ただし、非常に大きい数は、Cの処理範囲を超えます。そういうことは 考えなくてよいです）


アルゴリズム3（各桁の数を加算した値が3の倍数にあたるのかを確認する作戦) 
（各桁を加算した値を、%3するのもよいが、2つの数を加算しながら、 3で割った余りを得ていく作戦） 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

int main(void) { 
    char s[100]; 
    int n; /* 整数 n */ 
    int m; /* m桁 */ 

    /* 先に、0,1,2と0,1,2,3,4,5,6,7,8,9を加算した値の3の余りを作成 */ 
    int table[3][10] = {{0,1,2,0,1,2,0,1,2,0},{1,2,0,1,2,0,1,2,0,1}, {2,0,1,2,0,1,2,0,1,2}}; 
    int i; /* 各桁 */ 
    int r; /* 3で割った余り */ 
    int d; /* 各桁の1桁整数 */ 

    printf("n ? "); 
    scanf("%s", s); /* 文字列として受け取る */ 
    n = atoi(s); /* 数の文字列を１つの整数に変換する関数 */ 
    m = strlen(s); /* 文字列の長さを得る。m桁がわかる */
    
    printf("\nn = %d\n", n); 
    printf("m桁 : %d\n", m); 

    i = 0; /* i桁目。最上位の桁から */ 
    r = 0; /* 3で割った余り。初期値は0 */ 

    while (s[i] != '\0') { /* 整数としてはいくつなのかをアスキーコードから計算 */ 
        d = s[i] - 48; 
        r = table[r][d]; /* rとdの組み合わせから、3の余りを求める */ 
        printf ("r = %d, d = %d\n", r, d); 
        i++; /* 次の桁へ */ 
    } 

    if (r == 0) 
        printf("3の倍数です\n"); 
    else 
        printf("3の倍数ではありません\n"); 

    printf ("r = %d\n", r); 

    return 0; 
} 
このプログラムのwhileループ数は、nの大きさではなくて、nの桁数mに比例する。 
たとえば、n=1000とn=9000を比較すると、とぢらも4桁なので、計算時間は等しい。 
桁数に比例するということは、logに比例するということである。
（底を10とするとき、log 1 は0, log 100は、2, log 10000は4. 
n = 100とn = 10000を比較すると、nが100倍になったが、logは2倍