課題1.4

課題

  1. 整数 n について、nが3の倍数であるかどうかを判定する問題を考えよう。この問題を解決するアルゴリズム（解法、手順）を、プログラミングしなさい。
  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として読み込んで、桁数を求める方法もある]

コメント

同じ問題に、異なるアルゴリズム（手順、解法）

  1. 偶数奇数判定がヒント
  2. 繰り返し引き続けて、、
  3. まだ、あるかな

あなたのアルゴリズムの処理時間は、どのように増加していくだろう 。nが大きくなると、処理時間はどのように増加するだろうか。どの基本関数の増加の仕方に近いか。

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

1. 2. の方法ではないアルゴリズムに使いそうなプログラム　（参考のプログラムです）

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

#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 ? \n");
    scanf("%s", s);  /* 入力した数は、文字列に */

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

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

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

    return 0;
}