はじめに

どうも、Javaおじさんです。

正直あんまり初日に張り切ると後が続かないので投稿は1日1回にしておこうかな、とは思っています。
とはいえ一応読み進めてはいるのとコード書かないと覚えられる気がしないのでコツコツ書いていこう。

で、(その1)のコメントで親切な方がエレガントに書いてくれたんだけど（感謝！）、
rangeって等差数列だけじゃなくて公差数列も書けるはずよな...
それ使えないと一部アルゴリズム書けないよな...と思って
ひねくれてrangeで公差数列使うバージョン書いてみた。

3-1-B.py

while True:
    origin = int(input('正の整数を入力してください ： '))
    if origin > 0:
        break
    print('正の整数だって言ってんだろ')

found = False
print('元の数', origin)
for pwr in range(2, 6):
    for root in range(origin, 1, -1):
        if origin == root**pwr:
            print('root', root, 'pwr', pwr)
            found = True

if not found:
    print('該当する組み合わせは見つかりませんでした')

これで同等に動く。
でもこれアルゴリズムに必要性ない時に多用する表現じゃないね。
単にパラメータが1個増えるだけとはいえ面倒だし可読性も高くないし。
今回のは普通に両方等差数列のrange使えば何の問題もない話。

まあなんですか、プログラミング言語覚えるためにはこういう試行錯誤大事よねって話。

続いてのお題

さて、実はfor ... in range用のお題は別にあって、こういうもの。

小数を含む文字列(例：'1.4, 19.2, 7.8')をコンマで分けたうえ、その合計を求め、それを表示するプログラムを書け。

訳注には「ここまでの知識だと結構難しいよ」とか書かれているけど「結構」ですむのかよｗ
いわゆるString#split的な関数探す必要あるじゃないの。
と思ったら巻末に簡易リファレンスが載っててあっさり解決。
split関数あるんじゃん。
「分割したリストを返してくれる」ってことはあれでしょ、文字列同様lenで要素数が取れて添字でアクセスできるんでしょ？
と言って書いたのがこれ。

3-2.py

origin = '1.4, 19.2, 7.8'

textList = origin.split(',')
total = 0.0
for i in range(0, len(textList)):
    total += float(textList[i])

print('合計は', total)

実行させるとこうなる。

合計は 28.4

うん、動くね。
若干釈然としないのは、listの中にあったcountとかindexとかは使えないのかしら、という疑問。
まあそれは多分このテキストだと後から出てくるんだろうなー。
でもなー、「北斗の文句は俺に言え」ならぬ「オブジェクトのことはオブジェクトに聞け」がオブジェクト指向の基本概念だと思うんだけど、list自身のメソッド使わないのどうなのかしらね。

追記：
と思ったら、またコメントで素敵解法が。
そうか、そりゃそうよね。Javaの拡張for文もリストから直接取り出せるんだったｗ
「金槌を握るとなんでも釘に見える」のいい例だこれｗ
mapとかについてはたぶんもうちょいテキスト進めば出てくる記法なので今はおいとこう。

二分探索法

えー、白状すると数学それほど得意じゃないです。
じゃなぜMIT教科書に手を出したんだって話なんだけども。

今度のお題は立方根の近似解を求める以下のプログラムを修正しろというお話。
ソースはテキストからの抜粋に立方根の計算になるよう手を加えたもの。
なんかごちゃごちゃしているように見えるが実はアルゴリズムそのものは二分探索法になっている。

3-3-source.py

x = 25
epsilon = 0.01
numGuesses = 0
low = 0.0
high = max(1.0, x)
ans = (high + low)/2.0
while abs(ans**3 - x) >= epsilon:
    print('low =', low, 'high =', high, 'ans =', ans)
    numGuesses += 1
    if ans**3 < x:
        low = ans
    else:
        high = ans
    ans = (high + low)/2.0
print('numGuesses =', numGuesses)
print(ans, 'is close to cube root of', x)

実行結果は以下の通り。

low = 0.0 high = 25 ans = 12.5
low = 0.0 high = 12.5 ans = 6.25
low = 0.0 high = 6.25 ans = 3.125
low = 0.0 high = 3.125 ans = 1.5625
low = 1.5625 high = 3.125 ans = 2.34375
low = 2.34375 high = 3.125 ans = 2.734375
low = 2.734375 high = 3.125 ans = 2.9296875
low = 2.734375 high = 2.9296875 ans = 2.83203125
low = 2.83203125 high = 2.9296875 ans = 2.880859375
low = 2.880859375 high = 2.9296875 ans = 2.9052734375
low = 2.9052734375 high = 2.9296875 ans = 2.91748046875
low = 2.91748046875 high = 2.9296875 ans = 2.923583984375
low = 2.923583984375 high = 2.9296875 ans = 2.9266357421875
low = 2.923583984375 high = 2.9266357421875 ans = 2.92510986328125
numGuesses = 14
2.924346923828125 is close to cube root of 25

で、お題は以下。

x = 25をx = -25に変更すると何が起きるか？
正と負、両方の立方根の近似を見つけられるようにするためにはどのように変更するべきか？

とりあえず変更してみると無限ループになる。
実行結果の詳細は省略。
なんで無限ループになるかというと、ansの3乗-xが常にepsilonを超えるから。
この辺は実際に計算してみると早いけど、~~これ書いてる時間が時間なのでまた明日書く、書きたい...書くんじゃないかな。たぶん~~こんな感じ。

初期化時の各変数の状態：
x=-25, min = 0.0, max=1.0, epsilon = 0.1, ans = (0.0+1.0)/2.0 = 0.5

この状態でループの条件ans^3 - xは0.5^3 - (-25) = 0.125+25になって余裕でepsilonを超える。
また1回目のループでansの値をlowかhighかに入れ替える部分

    if ans**3 < x:
        low = ans
    else: 
        high = ans
    ans = (high + low)/2.0

ここについては
ans^3 < x　は　0.5^3 < -25
になるので
highの値が1→0.5になってその結果ans = 0.25となる。

この後は常にループの条件がans^3+25 >= epsilonでtrueになる上に、ans^3よりも必ずxの方が小さくなるので
highが0に向かって収束していき、結果としてansの値もどんどん0に近づいていく。
結果めでたく無限ループの出来上がりというわけだ。

なので、無限ループにならないようxが負数の場合にlowとhighを入れ替える措置をとる。
こうすることで、今度はxの値がminに反映されて正しくアルゴリズムが動くはず。

3-3-negative.py

x = -25
epsilon = 0.01
numGuesses = 0
if x > 0:
    low = 0.0
    high = max(1.0, x)
else:
    low = min(-1.0, x)
    high = 0.0

ans = (high + low)/2.0
while abs(ans**3 - x) >= epsilon:
    print('low =', low, 'high =', high, 'ans =', ans)
    numGuesses += 1
    if ans**3 < x:
        low = ans
    else: 
        high = ans
    ans = (high + low)/2.0
print('numGuesses =', numGuesses)
print(ans, 'is close to cube root of', x)

これを実行してみると以下の解を得る。

low = -25 high = 0.0 ans = -12.5
low = -12.5 high = 0.0 ans = -6.25
low = -6.25 high = 0.0 ans = -3.125
low = -3.125 high = 0.0 ans = -1.5625
low = -3.125 high = -1.5625 ans = -2.34375
low = -3.125 high = -2.34375 ans = -2.734375
low = -3.125 high = -2.734375 ans = -2.9296875
low = -2.9296875 high = -2.734375 ans = -2.83203125
low = -2.9296875 high = -2.83203125 ans = -2.880859375
low = -2.9296875 high = -2.880859375 ans = -2.9052734375
low = -2.9296875 high = -2.9052734375 ans = -2.91748046875
low = -2.9296875 high = -2.91748046875 ans = -2.923583984375
low = -2.9296875 high = -2.923583984375 ans = -2.9266357421875
low = -2.9266357421875 high = -2.923583984375 ans = -2.92510986328125
numGuesses = 14
-2.924346923828125 is close to cube root of -25

xを25にしても問題なく稼働する。

low = 0.0 high = 25 ans = 12.5
low = 0.0 high = 12.5 ans = 6.25
low = 0.0 high = 6.25 ans = 3.125
low = 0.0 high = 3.125 ans = 1.5625
low = 1.5625 high = 3.125 ans = 2.34375
low = 2.34375 high = 3.125 ans = 2.734375
low = 2.734375 high = 3.125 ans = 2.9296875
low = 2.734375 high = 2.9296875 ans = 2.83203125
low = 2.83203125 high = 2.9296875 ans = 2.880859375
low = 2.880859375 high = 2.9296875 ans = 2.9052734375
low = 2.9052734375 high = 2.9296875 ans = 2.91748046875
low = 2.91748046875 high = 2.9296875 ans = 2.923583984375
low = 2.923583984375 high = 2.9296875 ans = 2.9266357421875
low = 2.923583984375 high = 2.9266357421875 ans = 2.92510986328125
numGuesses = 14
2.924346923828125 is close to cube root of 25

でもまあこれ自分で全部一から実装したわけでないから目標達成とはならんよね。
まだ文法全部見れてないしｗ

とりあえず今夜はここまで。