C言語関係掲示板

過去ログ

No.466.『奇数なら3倍し、1をたす』、『偶数なら、半分にする』繰り返す

[戻る] [ホームページ]
No.3375

教えてください。
投稿者---秋也(2002/11/08 12:22:06)


#include <stdio.h>
main(){

int a,k,y,k_max,y_max;

for(y=1;y<1000000;y++)

a=y;
k=0;

while(a>1){

if(a%2==0){
a=a/2;
++k;
}
else{
a=a*3+1;
++k;
}
}

if(y==1 || k>k_max){
k_max=k;
y_max=y;
}
}
printf("yが%dのときkの最大値は%です。\n",y_max,k_max);
}

ある正数yが1になるまで、『奇数なら3倍し、1をたす』、『偶数なら、半分にする』繰り返した回数をkとして1〜1000000までのkの最大値とそのときのyをだすプログラムです。
今度、これを『1〜100までの結果を配列に蓄え、以降の計算に利用する』プログラムを作りたいのですが、どのようにすればよいのでしょう?おしえてください。

No.3377

Re:教えてください。
投稿者---かずま(2002/11/08 13:54:09)


> 繰り返した回数をkとして1〜1000000までのkの最大値と
> そのときのyをだすプログラムです。

そのプログラムは、int が 32ビットの場合、1〜113382 でしか正しい答えを
出しません。次のプログラムを実行してみると分かるでしょう。
int main()
{
    int a, k, y = 113383;

    a = y;
    k = 0;
    while (a > 1) {
        if (a%2 == 0)
            a = a/2;
        else
            a = a*3 + 1;
        ++k;
        printf("%d: %d\n", k, a);
    }
    return 0;
}


No.3378

Re:教えてください。
投稿者---aki(2002/11/08 14:37:02)


>ある正数yが1になるまで、『奇数なら3倍し、1をたす』、『偶数なら、
>半分にする』繰り返した回数をkとして1〜1000000までのkの最大
>値とそのときのyをだすプログラムです

3倍して1を足す計算はどんな数に対しても出来るとは限りません。aが大きい
場合にはオーバーフローしてしまうかもしれません。それを考慮すると次のよ
うなプログラムになります。考慮といっても計算できなかったということを
報告するだけですが。

#include <stdio.h>
#include <limits.h>

int collatz(long n)
{
    int count;

    for (count = 0; n != 1; count++) {
        if (n % 2 == 0)
            n /= 2;
        else if (n <= (LONG_MAX - 1) / 3)
            n = 3 * n + 1;
        else
            return -1;
    }
    return count;
}

int main(void)
{
    long i, i_max = 0;
    int  k, k_max = 0;

    for (i = 1; i <= 1000000; i++) {
        if ((k = collatz(i)) < 0)
            printf("i = %ldは計算中にオーバフローが発生します。\n", i);
        if (k > k_max)
            i_max = i, k_max = k;
    }
    printf("計算可能なiについて、");
    printf("i = %ldのとき、kは最大値%dをとる", i_max, k_max);
    return 0;
}

>今度、これを『1〜100までの結果を配列に蓄え、以降の計算に利用する』
>プログラムを作りたいのですが、どのようにすればよいのでしょう?おしえ
>てください。

int main(void)
{
    int i, k[100+1];

    for (i = 1; i <= 100; i++)
        k[i] = collatz(i);

    for (i = 1; i <= 100; i++)
        printf("k[%d]\t= %d\n", i, k[i]);
    return 0;
}


No.3381

お二人へ
投稿者---秋也(2002/11/08 17:05:14)


intをuninteger(intのマイナス部分をなくしプラスの表現範囲を増やす)のにかえてください。(つづりはこうだと思います。)そしたらできますよね。そこから、『1〜100までの結果を配列に蓄え、以降の計算に利用する』プログラムをつくりたいのです。

No.3383

Re:お二人へ
投稿者---aki(2002/11/08 17:24:37)


>intをuninteger(intのマイナス部分をなくしプラスの表現範囲を増やす)のにか
>えてください。(つづりはこうだと思います。)

unsigned int のことでしょうか。

>そしたらできますよね。

できません。int のビット数を32と仮定した場合、その程度じゃまるで無理
です。unsigned int で扱える正の数の範囲は int の倍程度です。

>そこから、『1〜100までの結果を配列に蓄え、以降の計算に利用する』
>プログラムをつくりたいのです。

それについてはもう書きました。


No.3394

Re:お二人へ
投稿者---aki(2002/11/09 23:13:12)


>>そこから、『1〜100までの結果を配列に蓄え、以降の計算に利用する』
>>プログラムをつくりたいのです。
>
>それについてはもう書きました。

意味がわかってませんでした。すみません。


No.3391

Re:お二人へ
投稿者---かずま(2002/11/09 21:13:48)


double を使うと、2の53乗までの整数は正確に扱えるので、オーバーフローしません。
100までの値を配列に憶えておいて利用すると、実行時間は3分の2に短縮されるようです。
#include <stdio.h>
#include <math.h>

int main(void)
{
    double  y, y_max = 0, a;
    int     k, k_max = 0;

    for (y = 1; y <= 1000000; y++) {
        for (a = y, k = 0; a > 1; k++)
            a = fmod(a, 2) ? (a * 3 + 1) : (a / 2);
        if (k > k_max)
            y_max = y, k_max = k;
    }
    printf("y = %.16g のとき、k は最大値 %d をとる", y_max, k_max);
    return 0;
}
----------------------------------------------------------------------
#include <stdio.h>
#include <math.h>

int main(void)
{
    double  y, y_max = 0, a;
    int     k, k_max = 0, k_tab[101];

    for (y = 1; y <= 100; y++) {
        for (a = y, k = 0; a > 1; k++)
            a = fmod(a, 2) ? (3 * a + 1) :(a / 2);
        if (k > k_max)
            y_max = y, k_max = k;
        k_tab[y] = k;
    }
    for (y = 101; y <= 1000000; y++) {
        for (a = y, k = 0; a > 100; k++)
            a = fmod(a, 2) ? (3 * a + 1) :(a / 2);
        k += k_tab[a];
        if (k > k_max)
            y_max = y, k_max = k;
    }
    printf("y = %.16g のとき、k は最大値 %d をとる", y_max, k_max);
    return 0;
}


No.3395

Re:お二人へ
投稿者---かずま(2002/11/10 03:32:43)


>        k_tab[y] = k;

>        k += k_tab[a];
BC++ では問題ないのですが、VC++ や gcc では、添え字が整数ではない、
というエラーになるようです。次のようにキャストが必要です。
        k_tab[(int)y] = k;

        k += k_tab[(int)a];

さて、配列の大きさを大きくすれば、もっと高速化されるわけで、
4MB ぐらいは平気で取れるようなので、次のようにしてみました。
#include <stdio.h>
#include <math.h>

#define MAX_TAB  1000000 /* 101, 1000, 10000, 100000 */

int k_tab[MAX_TAB];

int main(void)
{
    double  y, y_max = 0, a;
    int     k, k_max = 0, m = 1;

    k_tab[1] = 0;
    for (y = 1; y <= 1000000; y++) {
        for (a = y, k = 0; a > m; k++)
            a = fmod(a, 2) ? (3 * a + 1) :(a / 2);
        k += k_tab[(int)a];
        if (k > k_max)
            y_max = y, k_max = k;
        if (y < MAX_TAB)
            k_tab[(int)y] = k, m = y;
    }
    printf("y = %.16g のとき、k は最大値 %d をとる", y_max, k_max);
    return 0;
}