スペースアルクのアイコンリンクをはずしてみた。

　スペースアルクのアイコンリンクがリンク切れになっていたのではずしてみました。(^_^;

知恵袋で見つけた「自然数を順番に並べた数」の問題をPythonで解いてみた。

　知恵袋で見つけた「自然数を順番に並べた数」の問題をPythonで解いてみました。

全ての自然数を順番に並べて書いたとする。（下のように）
123456789101112131415161718192021・・・
このように並べると、例えば、10番目の数字は1であり、32番目の数字は2である。
では、100万番目の数字は何でしょうか？

　まず、1から始まる次のように段になった群数列を考えます。元になる整数ごとに、群に分け、さらにその群を桁数ごとに段に分けます。

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 1 0 | 1 1 | 1 2 | ... | 9 9 |
| 1 0 0 | 1 0 1 | 1 0 2 | ... | 9 9 9 |
| 1 0 0 0 | 1 0 0 1 | 1 0 0 2 | ...| 9 9 9 9 |
| 1 0 0 0 0 | 1 0 0 0 1 | 1 0 0 0 2 | ...| 9 9 9 9 9 |
...

　1段目は9個、2段目は90個、3段目は900個…で、第ｎ段の群数は個であり、第ｎ段の群はどれもｎ個の項を含んでいるので、第ｎ段の末項までの項数は、
　
これを使えば、前からn番目の数(項)が第何段にある(属する)かを調べることができます。
　また、属する段で第何群目かを調べて、前からn番目の項が前から通して第何群にあるのかとその群の末項までの項数が分かると題意の「ｎ番目の数字」を求めることができます。
　次に、検算用の別解を検索していたら、オンライン整数列大事典でいいのを見つけました。それによると、チャンパーノウン定数に関連があるようです。ここに出ている下の式をちょっと変形して、整数だけで計算できるように、Ceil2(x,y)関数を作って、検算用の関数を作りました。

　mod(floor(10^(mod(n+(10^i-10)/9,i)-i+1)*ceiling((9*n+10^i-1.0)/(9*i)-1)),10)

　ちなみに、検算用の方がちょっと速いようです。(^_^;

● Champernowne2.py

# coding: UTF-8
# Champernowne2.py

from time import time
from math import log10

# 第n段の末項までの項数を求める
def kosDanLst(n):
    return n*10**n+(1-10**n)//9

# 前からn番目の項が第何段に属するか求める
def getDan(n):
    if n<=1: return 1
    #j=log10(n); i=int(j-log10(j))+1
    i=int(log10(n)-log10(log10(n)))+1
    while kosDanLst(i)< n:
         i+=1
    return i

# 前からn番目の項が前から第何群にあるか調べてその群の末項までの項数を求める
def getGunAndKosGunLst(n):
    k=getDan(n)
    j=kosDanLst(k-1)    # 第(k-1)段の末項までの項数
    i=Ceil2(n-j,k)      # 属する段で第何群目かを調べる
    return 10**(k-1)+i-1, j+k*i

# x の 10**n の位の数を取り出す
def getNum(x,n):
    return (x//10**n)%10

# n番目の数字(項)
def NthChampernowne(n):
    i,j=getGunAndKosGunLst(n)
    return getNum(i,j-n)

# 検算用
def NthChampernowne2(n):
    i=getDan(n) # 何段目にあるか調べる
    j=9*n+10**i-1
    return getNum(Ceil2(j,9*i)-1,i-1-(j//9-1)%i)

def Ceil2(x,y):
    return x//y if x % y==0 else x//y+1

def main():
    pass # code goes here
    tm=time()  # Timer Start
    s = t = ""
    for n in range(1,34):
        s+="%d "%NthChampernowne(n)
    print(s[:-1])
    for n in range(1,34):
        t+="%d "%NthChampernowne2(n)
    print(u"%s… 検算"%t)
    m = 1000000
    print(u"100万番目: %d"%NthChampernowne(m))
    print(u" 〃(検算): %d"%NthChampernowne2(m))
    tm=time()-tm  # Timer Stop
    print("Runtime : %.3f [sec]"%tm)

if __name__ == '__main__':
    main()

●実行結果

1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1
1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 2 1 … 検算
100万番目: 1
 〃(検算): 1
Runtime : 0.016 [sec]

※参考URL
http://mathworld.wolfram.com/ChampernowneConstant.html
●知恵袋で見つけた「自然数を順番に並べた数」の問題をJavaで解いてみた。

パーフェクトPython (PERFECT SERIES 5)

知恵袋の最大公約数・最小公倍数の問題をPythonで解いてみた。

　知恵袋の最大公約数・最小公倍数の問題をPythonで解いてみました。(^_^;

n,125,175の最大公約数が25,最小公倍数が3500をみたす自然数nを求めよ。

　ｎの範囲は、25≦ｎ≦3500で、あとは、3数のgcdとlcmを求めてチェックするだけです。(^_^;

● GcdAndLcm1.py

# coding: UTF-8
# GcdAndLcm1.py

from functools import reduce
from fractions import gcd

def Gcd(numbers):
    return reduce(gcd,numbers)

def Lcm(numbers):
    return reduce(lambda x,y: (x*y)//gcd(x,y),numbers,1)

def main():
    pass # code goes here
    for n in range(25,3500+1):
        lst=[n,125,175]
        if Gcd(lst)==25 and Lcm(lst)==3500:
            print(n)

if __name__ == '__main__':
    main()

●実行結果

100
500
700
3500

※参考URL
http://d.hatena.ne.jp/rsc96074/20140127/1390834236
●RiK0 Tech Temple: Nice functional LCM in Python

Pythonスタートブック

質問の期待値の問題をPythonで解いてみた。

　昨日のJavaのプログラムをPythonに翻訳してみました。(^_^;
　ちょっと遅いけど、やっぱり、楽だねぇ。

● ExpectedValue1.py

# coding: UTF-8
# ExpectedValue1.py

import itertools
from time import time
from fractions import Fraction

def countRen(c):
    count=1
    for i in range(len(c)-1):
        if c[i]!=c[i+1]:
            count+=1
    return count

def main():
    pass # code goes here
    tm=time()  # Timer Start

    p = list('AAAAABBBBB')
    r = len(p)
    count = [0]*r
    total = 0
    for q in list(set(itertools.permutations(p,r))): # 同じものを含む順列
        total+=1
        count[countRen(q)-1]+=1

    numerator = 0
    for i in range(r):
        print("%2d:%3d"%(i+1,count[i]))
        numerator += (i+1)*count[i]
    print(u"∴ %d / %d = %s"%(numerator,total,Fraction(numerator,total)))

    tm=time()-tm  # Timer Stop
    print("Runtime : %.3f [sec]"%tm)

if __name__ == '__main__':
    main()

●実行結果

 1:  0
 2:  2
 3:  8
 4: 32
 5: 48
 6: 72
 7: 48
 8: 32
 9:  8
10:  2
∴ 1512 / 252 = 6
Runtime : 1.106 [sec]

Pythonスタートブック

パーフェクトPython (PERFECT SERIES 5)

初めてのPython 第3版

質問の期待値の問題をJavaで解いてみた。

　質問の期待値の問題をJavaで解いてみました。(^_^;

　2種の文字A,Bの順列について考える　同一文字の1つづきを1つの連という
　例えばAABABB ではAA,B,A,BBの4個の連を持つ
　A,Bを5個ずつ計10個を1列に並べるときの連の個数の期待値を求めよ

※参考URL
http://okwave.jp/qa/q8808555.html

　{連の個数}＝({文字の変わり目}+1)[個]で計算しました。(^_^;
　連の個数の最大値は10、最小値は2で、1の分は不要ですが、1の分も含めて、連の個数が1〜10になる場合の数をそれぞれカウントした結果も表示するようにしました。
　ちなみに、計算式を書くと次の通りです。(^_^;

● ExpectedValue1.java

/* 
 * ExpectedValue1.java
 * 
 */

public class ExpectedValue1 {
    // 順列生成
    static boolean nextPerm(char[] p, int n, int r) {
        int i, j;
        char t;
        
        if(r <= 0 || n < r) return(false);
        for(i = r + 1; i <= n-1; i++)
            for(j = i; j >= r + 1 && p[j-1] < p[j]; j--){
                t = p[j]; p[j] = p[j-1]; p[j-1] = t;    // swap(p,j,j-1);
            }
        for(i = n - 1; i > 0 && p[i-1] >= p[i]; i--);
        if(i==0) return(false);
        for(j = n - 1; j > i && p[i-1] >= p[j]; j--);
        t = p[j]; p[j] = p[i-1]; p[i-1] = t;            // swap(p,j,i-1);
        for(j = n - 1; i < j; i++, j--){
            t = p[i]; p[i] = p[j]; p[j] = t;            // swap(p,i,j);
        }
        return(true);
    }
    
    static int gcd(int a, int b){
        return( b == 0 ? a : gcd(b, a % b) );
    }
    
    static int countRen(char[] c){
        int count = 1;
        for(int i=0; i< c.length-1; i++)
            if(c[i]!=c[i+1])
                count++;
        return count;
    }
    
    public static void main(String[] args) {
        final String P = "AAAAABBBBB";
        final int N = P.length();
        char[] p = P.toCharArray();     // 順列生成用
        int total = 0, g=1;
        int[] count = new int[10];
        long tm=System.nanoTime();      // Timer Start
        do{
            total++;
            count[countRen(p)-1]++;
        }while(nextPerm(p,N,N));

        int numerator = 0;
        for(int i=0; i< count.length; i++){
            numerator += (i+1)*count[i];
            System.out.printf("%2d:%3d\n",i+1,count[i]);
        }
        if(numerator!=0) g=gcd(numerator, total);
        System.out.printf("∴%d / %d = %d / %d\n",numerator,total,numerator/g,total/g);
        tm=System.nanoTime()-tm;        // Timer Stop
        System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9);
    }
}

●実行結果

 1:  0
 2:  2
 3:  8
 4: 32
 5: 48
 6: 72
 7: 48
 8: 32
 9:  8
10:  2
∴1512 / 252 = 6 / 1
Runtime : 0.025 [sec]

拙ブログについてのアンケート

　皆さん、アンケートの回答ありがとうございました。
　票が割れてしまってわかりにくいですが、プログラム関係が一番人気のようです。その他が一番多いのもちょっと気になりますが、打たれ弱いので深く考えないことにします。(^_^;
　集計を取ってみると、女性ではおススメ本が一番人気のようなので、もっと、おススメ本ネタを書いてみようかなぁ。(^_^;

必ず結果が出るブログ運営テクニック100 プロ・ブロガーが教える“俺メディア"の極意

ブログ飯 個性を収入に変える生き方

質問のくじ引きの確率の問題をJavaで解いてみた。

　質問のくじ引きの確率の問題をJavaで解いてみました。(^_^;

10本のくじの中に3本の当たりくじと1本のチャンスくじとがある　チャンスくじを引いたときは引き続きもう一度ひくものとする　甲、乙の順でくじをひくとき、それぞれお当たりくじを引く確率を求めよ　ただし、1回に1本ずつくじをひき、引いたくじは元に戻さないとする

※参考URL
http://oshiete.goo.ne.jp/qa/8792630.html
http://okwave.jp/qa/q2118560.html

　くじにa〜jの名前を付けて、a,b,cを当たりくじ(○)、dをチャンスくじ(△)、e,f,g,h,i,jをはずれくじ(×)としました。当たりはずれの判定は、char型の大小比較を用いました。a,b,c < d < e,f,g,h,i,j
　また、順列を生成するのに、チャンスくじdを含む場合と含まない場合で引く回数(nPrのrに相当)が異なるので場合分けしました。

● Lottery1.java

/*
 * Lottery1.java
 * 
 */

class Lottery1 {
    static boolean nextPerm(char[] p, int n, int r) {
        int i, j;
        char t;
        
        if(r <= 0 || n < r) return(false);
        for(i = r + 1; i <= n-1; i++)
            for(j = i; j >= r + 1 && p[j-1] < p[j]; j--){
                t = p[j]; p[j] = p[j-1]; p[j-1] = t;    // swap(p,j,j-1);
            }
        for(i = n - 1; i > 0 && p[i-1] >= p[i]; i--);
        if(i==0) return(false);
        for(j = n - 1; j > i && p[i-1] >= p[j]; j--);
        t = p[j]; p[j] = p[i-1]; p[i-1] = t;            // swap(p,j,i-1);
        for(j=n-1; i< j; i++, j--){
            t = p[i]; p[i] = p[j]; p[j] = t;            // swap(p,i,j);
        }
        return(true);
    }
    
    static int gcd(int a, int b){
        return( b == 0 ? a : gcd(b, a % b) );
    }
    
    public static void main(String[] args) {
        final String P = "abcdefghij";  // ○a,b,c,△d,×e,f,g,h,i,jとする
        char[] p = P.toCharArray();     // 順列生成用
        int n = p.length;
        int total = 0, countKou = 0, countOtu = 0, g = 1;
        long tm = System.nanoTime();    // Timer Start
        
        //--- チャンスくじ d を含まない場合 ---//
        do{
            if(p[0]=='d' || p[1]=='d') continue;
            total++;
            if(p[0]< 'd') countKou++;
            if(p[1]< 'd') countOtu++;
        }while(nextPerm(p,n,2));
        //--- チャンスくじ d を含む場合 ---//
        p = P.toCharArray();
        do{
            if(p[0]!='d' && p[1]!='d') continue;
            total++;
            if(p[0]< 'd' || p[1]< 'd') countKou++;
            if(p[2]< 'd')              countOtu++;
        }while(nextPerm(p,n,3));        
        g = gcd(total, countKou);
        System.out.printf("(甲) %d / %d = %d / %d\n", countKou, total, countKou/g, total/g);
        g = gcd(total, countOtu);
        System.out.printf("(乙) %d / %d = %d / %d\n", countOtu, total, countOtu/g, total/g);
        tm=System.nanoTime()-tm;        // Timer Stop
        System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9);
    }
}

●実行結果

(甲) 72 / 216 = 1 / 3
(乙) 72 / 216 = 1 / 3
Runtime : 0.022 [sec]

スッキリわかるJava入門 第2版 (スッキリシリーズ)

わかりやすいJava入門編