Skip to content.

kagome.lab.tkikuchi.net

Sections
Personal tools
You are here: Home » Members » tkikuchi's Home » 授業 » アルゴリズムとデータ構造C » データ構造とアルゴリズムの基礎（続き）
Views

データ構造とアルゴリズムの基礎（続き）

Document Actions
アルゴリズム、プログラミング言語、プログラムの処理

先週、積み木にはまったので

  • 今回は一気に1章を終わる

たとえば

  • 最大公約数を求める
    • 最大公約数は小さいほうの数に等しいかより小さい
    • 小さいほうの数から始めて１ずつ減らして確かめる

アルゴリズム（流れ図）

ユークリッド(Euclid)の互除法

  • 剰余を求めていく

再帰的アルゴリズム

  • Recursive
  • 数学的帰納法と同じ
  • def rgcd(a, b):
    if b == 0:
        return a
    else:
        return rgcd(b, a % b)

計算量

  • O(n) ... n に比例
  • O(n2) ... n の2乗に比例
  • O(log n) ... log n に比例
  • O(n log n) ... n log n に比例
  • O(na)
  • O(an) ... n 大で手に負えない
  • O(n!) ... 同上

プログラミング言語

  • Python 特徴
  • begin end { } ; が無い
  • インデント、改行でプログラムの構造を決める
  • 変数の型が無い
  • オブジェクトに型がある

golden を python で書いてみる

  • def increment(a, k, x):
    b = a
    for i in range(k):
        b = a + b
        a = b - a
        x = float(b) / a
    print "%5d %5d %10.5f" % (a, b, x)
　
n, times = raw_input("input n and times: ").split()
n = int(n)
times = int(times)
ratio = 0.
if n > 0:
    increment(n, times, ratio)
    print "%5d %5d %10.5f :main" % (n, times, ratio)

ちなみに

プログラム言語にあるもの

  • 代入
  • 関数（又は関数と手続き）
  • 条件分岐
  • 繰り返し

代入

  • a := b (Pascal/ALGOL)
  • a = b (C/Python)

関数

  • 戻り値が無い ... 手続き (Pascal)
  • 戻り値はひとつ ... 関数の型宣言 (C)
  • 戻り値はオブジェクト ... Python
    • return x, y （タプルオブジェクト）

条件分岐

  • if / if ... else
  • switch / case
  • if ... elif ... elif ... else

繰り返し

  • while 条件 (do) ...
  • repeat ... until 条件
  • 2番目の型は while 1 ... if 条件 break

Call by ...

  • call by value ... 値呼び出し
    • 元の変数値は変わらない
  • call by reference ... 参照呼出し
    • 関数内での操作によって変数の値が変わる

C 言語の場合

  • int val(int x) {
    x = x + x;
    return x;
}
　
main() {
    int x, y;
　
    x = 1;
    y = val(x);
    printf("%d %d\n", x, y);
}
  • 出力 ... 1 2

C 言語の場合(2)

  • int val(int ＊x) {
    ＊x = ＊x + ＊x;
    return ＊x;
}
　
main() {
    int x, y;
　
    x = 1;
    y = val(&x);
    printf("%d %d\n", x, y);
}
  • 出力 ... 2 2

Python では？

  • 変数は全てオブジェクトへの reference
  • では、Ｃの(2) になるか？
  • 変更可能 (mutable) 変更不可能 (immutable) によって違う

変更不可能の場合

  • def immutable(x):
    x = x + x
    return x
　
x = 1
y = immutable(x)
print x, y
  • 出力 ... 1 2

変更可能の場合

  • def mutable(x):
    x[0] = x[0] + x[0]
    return x
　
x = [1]
y = mutable(x)
print x, y
  • 出力 ... [2] [2]

本日の問題

  • ユークリッドのアルゴリズムを用いて、次の２つの数の最大公約数を求めなさい。
  • 自分の生（年）月日から3ないし4桁の整数を作る
    • 5月5日なら 505
  • 今日の日付（425）
  • 次週は連休の間で休講・次回の講義は5月9日

回答例

  • 505 % 425 = 80
  • 425 % 80 = 25
  • 80 % 25 = 5
  • 25 % 5 = 0
  • よって GCD = 5

一番大きかった人

  • 1020 % 425 = 170
  • 425 % 170 = 85
  • 170 % 85 = 0
  • GCD = 85
  • 惜しいことに計算ミスしてました。
Created by tkikuchi
Last modified 2006-06-09 15:25
 
Powered by Plone

This site conforms to the following standards: