日記「芦」

腐る一歩手前、紙一重のところが鴨肉の一番うまいときなのです(中島らも著「超老伝　カポエラをする人」より) 2003年の記事への解答 2011/8/4(Thu.)

『既約分数クイズ』
http://www.hyuki.com/dig/frac.html
に対しての解答。

下にコードを書きました。
まんまエラトステネスの篩です。
計算量はO(N^3)なんだけど、他の方の解答見ても大体そうだし、こんなもんだよね。

分母が1～N, 分子が0～N であるN(N+1)コの分数が候補だとし、
N*(N+1)の表を0と1で埋める。0がOKで1がNG。

分母がiのN+1コを見て行って、それが0以上であるコトは間違いないけど
1を超えてる場合は問答無用でNG。
q/pがOKな時(例えばp,q=1,0 , 2,1)、
k=1,2..として(q*k)/(p*k) はNGである。
つまり既約分数ではないから。

ただそれを繰り返すだけ。

function WITT(N){
    table=[];//表
    for(i=0;i<N;i++){table[i]=[];for(j=0;j<=N;j++)table[i][j]=0;}
	//表の初期化

    for(i=1;i<=N;i++){
        for(j=0;j<=N;j++){
            if(j/i>1)table[i-1][j]=1;
            if(table[i-1][j]==0){
                for(k=2;i*k<=N&&j*k<=N;k++)table[i*k-1][j*k]=1;
            }
        }
    }
    return table;
}
function display(table){
    write(table.map(function(a){return a.join(",")}).join("\n"));
}

table=WITT(10);
display(table);

コメ(0) | トラ(0)

---