C言語でProject Euler(プロジェクト・オイラー)に挑戦

上記の広告は１ヶ月以上更新のないブログに表示されています。新しい記事を書く事で広告が消せます。

Project Euler(プロジェクトオイラー)のproblem19☆
C言語を使っています。

/* Problem 19 † */
/*
次の情報が与えられている。

・1900年1月1日は月曜日である。
・9月、4月、6月、11月は30日まであり、2月を除く他の月は31日まである。
・2月は28日まであるが、うるう年のときは29日である。
・うるう年は西暦が4で割り切れる年に起こる。

しかし、西暦が400で割り切れず100で割り切れる年はうるう年でない。
20世紀（1901年1月1日から2000年12月31日）で月の初めが日曜日になるのは何回あるか。
*/


#include <stdio.h>
#include <conio.h>
int uruChk(int);

int uruChk(int yyyy)
{
    if(yyyy % 400 != 0 && yyyy % 100 == 0)
        return 28;
    else if(yyyy % 4 == 0)
        return 29;
    else
        return 28;
}

int main(void)
{
    int y, m, d;
    int i, cnt = 0;
    int d1;

    i = 0;

    for(y = 1900; y <= 2000; y++){
    for(m = 1; m <= 12; m++){
            if(m == 9 || m == 4 || m == 6 || m == 11)
                d1 = 30;
            else if(m == 2)
                d1 = uruChk(y);
            else
                d1 = 31;

            for(d = 1; d <= d1; d++){
                i++;
                if(i % 7 == 0){
                    if(d == 1 && y >= 1901)
                        cnt++;
                    i = 0;
                }
            }
        }
    }

    printf("%d\n", cnt);

    getch();
    return 0;
}



<<解>>　171


Project Euler(プロジェクトオイラー)Problem19です。
C言語で書いています。

我ながら美しくないコード
そのまんま書いただけ・・って感満載

その上、解が合わない・・と思っていたら、求めるのは1900年からではなく、1901年からでした。

いかにも素人なコードなんですが、どうしたらいいんでしょう。
アドバイス等ありましたら、ぜひともご教授ください



☆応援お願いします☆

にほんブログ村

Project Euler(プロジェクトオイラー)のproblem12☆
C言語を使っています。


/* Problem 12 † */
/*
三角数の数列は自然数の和で表わされ、
7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である。

三角数の最初の10項は
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
となる。

最初の7項について、その約数を列挙すると、以下のとおり。

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

これから、7番目の三角数である28は、6個以上の約数をもつ最初の三角数であることが分る。
では、501 個以上の約数をもつ最初の三角数はいくらか。
*/


#include <stdio.h>
#include <conio.h>

int func(int);

int func(int num)
{
    int i = 1, j, cnt = 0;

    j = num;
    while(i < j){
        if(num % i == 0){
            j = num / i;
            if(i == j)
                cnt++;
            else
                cnt = cnt + 2;
        }
        i++;
    }

    return cnt;
}

int main(void)
{
    int num, cnt, i;

    num = 0;
    i = 1;

    while(1){
        num = num + i;
        i++;
        cnt = func(num);

        if(cnt >= 501)
            break;

    }

    printf("%d, %d\n", cnt, num);

    getch();
    return 0;
}




<<解>>　76576500 （約数 576個）


Project Euler(プロジェクトオイラー)Problem12です。
前に教えていただいてから
教えてください！！C言語でProject Euler 【Problem12】
今頃になってしまいました。

Project Euler(プロジェクトオイラー)Problem12、眺めていたら、教えていただいたのとは違う考えですが、ひらめいたので、自分なりにやってみました。

約数を求めるのに、割り切れるということは、もう片方の数字があるんだ！と。
例えば28の約数は、1, 2, 4, 7, 14, 28
2を求めれば14がでてくるし、4を求めれば7がでてくる、ということを利用しました。
6 × 6 = 36 という同じ数のパターンもあるので、そこは注意。

ん～約数とか素数とか、いろんな考え方があるんですね。
C言語に限ったことでなないけれど、アルゴリズムって難しいですね



☆応援お願いします☆

にほんブログ村

Project Euler(プロジェクトオイラー)のproblem18☆
C言語を使っています。


/* Problem 18 † */
/*
以下の三角形の頂点から下まで移動するとき、その数値の合計の最大値は23になる。

3
7 4
2 4 6
8 5 9 3

この例では 3 + 7 + 4 + 9 = 23

以下の三角形を頂点から下まで移動するとき、その最大の合計値を求めよ。

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

注: ここではたかだか 16384 通りのルートしかないので、すべてのパターンを試すこともできる。
Problem 67 は同じ問題だが100行あるので、総当りでは解けない。もっと賢い方法が必要である。
*/



#include <stdio.h>
#include <conio.h>
#define R 15
#define C 15

int func(int);
int sum, cnt;
int data[R][R]={
    {75},
    {95, 64},
    {17, 47, 82},
    {18, 35, 87, 10},
    {20, 4, 82, 47, 65},
    {19, 1, 23, 75, 3, 34},
    {88, 2, 77, 73, 7, 63, 67},
    {99, 65, 04, 28, 6, 16, 70, 92},
    {41, 41, 26, 56, 83, 40, 80, 70, 33},
    {41, 48, 72, 33, 47, 32, 37, 16, 94, 29},
    {53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14},
    {70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57},
    {91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48},
    {63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31},
    { 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23}
};

int func(int i)
{
    int num, j;

    if(i < 0)
        return sum;

    for(j=0; j<cnt-1; j++){
        num = data[i][j];
        if(data[i+1][j] < data[i+1][j+1])
            num += data[i+1][j+1];
        else
            num += data[i+1][j];

        data[i][j] = num;
    }

    for(j = 0; j < cnt-1; j++)
        printf("%d, ", data[i][j]);
    printf("\n");

    cnt--;

    func(i-1);
    return 0;
}

int main(void)
{
    int i, j;

    for(i=0; i<R; i++){
        for(j=0; j<C; j++)
            printf("%d, ", data[i][j]);
        printf("\n");
    }

    cnt = C;
    func(R-2);;

    getch();
    return 0;
}



<<解>>　1074


Project Euler(プロジェクトオイラー)Problem18です。
上から順番に最大値を探していけばいい！と思ったら大きな間違いでした

下から順番に、大きいほうを残して、上にあがって行く方法です。

少し期間があいてしまいました・・
がんばらねば☆C言語





☆応援お願いします☆

にほんブログ村

Project Euler(プロジェクトオイラー)のproblem14☆
C言語を使っています。


/* Problem 14 † */
正の整数に以下の式で繰り返し生成する数列を定義する。

n → n/2 (n が偶数)
n → 3n + 1 (n が奇数)

13からはじめるとこの数列は以下のようになる。
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

13から1まで10個の項になる。この数列はどのような数字からはじめても
最終的には 1 になると考えられているが、
まだそのことは証明されていない(コラッツ問題)

さて、100万未満の数字の中でどの数字からはじめれば一番長い数列を生成するか。
注意: 数列の途中で100万以上になってもよい


#include <stdio.h>
#include <conio.h>
#define MAX 1000000

unsigned int keisan(unsigned int);
unsigned int saiki(unsigned int);

unsigned int data[MAX];
unsigned int dt;

int cnt;

unsigned int keisan(unsigned int n){

    if(n%2 == 0)
        n = n/2;
    else
        n = 3*n + 1;
    return n;
}

unsigned int saiki(unsigned int n)
{
    cnt++;
//printf("%d, ", n);

    if(n == 1)
        return cnt;
    if(MAX < n)
        return saiki(keisan(n));
    if(data[n-1] != 0)
        return cnt + data[n-1]-1;

    return saiki(keisan(n));
}

int main(void)
{
    unsigned int n;
    int i, j, max_cnt, max_num;

    dt = 0;
    max_cnt = 0;

    data[0] = 1;
    for(i = 1; i<MAX; i++){
        data[i] = 0;
    }

    for(i = 1; i<=MAX; i++){
        cnt = 0;
        cnt = saiki(i);

        data[i-1] = cnt;

        if(max_cnt < cnt){
            max_cnt = cnt;
            max_num = i;
        }
    }

    printf("max %d, %d\n", max_cnt, max_num);

    getch();
    return 0;
}



<<解>>　837799


Project Euler(プロジェクトオイラー)Problem14です。
これがC言語の再帰かー

はじめ、そのまんま組んでみたら、時間がかかって使い物にならず・・・
この再帰呼び出しとやらを使ってみたら、一瞬で処理できました。

使い方あってるんですかね！？
C言語の再帰呼び出し、何かアドバイスあったら教えてください

できた！と思っても答えが合わないでずっと悩んでいたら、
項の数を出していました
なんて初歩的なミス・・・
ちなみに項の数は　525　です。



☆応援お願いします☆

にほんブログ村

Project Euler(プロジェクトオイラー)のproblem17☆
C言語を使っています。

私の解き方は C言語でProject Euler 【Problem17】 だったのですが、
コメントいただいたシーフードさんはまったく違うやり方でしたので、載せさせていただきます


/* Problem 17 †*/
1 から 5 までの数字を英単語で書けば/
one, two, three, four, five であり、
全部で 3 + 3 + 5 + 4 + 4 = 19 の文字が使われている。

では 1 から 1000 (one thousand) までの数字を
すべて英単語で書けば、全部で何文字になるか。

注: 空白文字やハイフンを数えないこと。
例えば、342 (three hundred and forty-two) は 23 文字、
115 (one hundred and fifteen) は20文字と数える。
なお、"and" を使用するのは英国の慣習。


#include <stdio.h>
#include <conio.h>

//十の位
int Teath(int number)
{
    if(number == 0)
        return 0;
    else if(number == 4 || number == 5 || number == 6)
        return 5;
    else if(number == 2 || number == 3 || number == 8 || number == 9)
        return 6;
    else
        return 7;
}
//一桁
int Check1(int number)
{
    if(number == 0)
        return 0;
    else if(number == 1 || number == 2 || number == 6)
        return 3;
    else if(number == 4 || number == 5 || number == 9)
        return 4;
    else
        return 5;
}
//二桁
int Check2(int number)
{
    int i, max = 0, k;

    if(number == 11 || number == 12)
        return 6;
    else if(number == 15|| number == 16)
        return 7;
    else if(number == 13 || number == 14 || number == 18 || number == 19)
        return 8;
    else if(number == 17)
        return 9;
    else if(number == 10)
        return 3;
    else{
        for(i = 0;i <= 1;i ++){
            k = number % 10;
            number /= 10;
            if(i == 0)
                max += Check1(k);
            else
                max += Teath(k);
        }
    return max;
    }
}

//三桁
int Check3(int number)
{
    int i, k, max = 0;

    i = number / 100;
    k = number % 100;

    max += Check1(i);
    max += Check2(k);

    if(number % 100 ==0)
        return max + 7;
    else
        return max + 10;
}

//桁チェック
int CheckNumber(int number)
{
    int flg = 0, i;

    i = number;

    while(i > 0){
        i /= 10;
    flg ++;
    }

    if(flg == 1)
        return Check1(number);
    if(flg == 2)
        return Check2(number);
    if(flg == 3)
    return Check3(number);
}

int main(void)
{
    int i, max = 0;

    for(i = 1;i <= 999;i ++){
        max += CheckNumber(i);
    }

    printf("%d\n",max + 11);
    getch();
    return 0;
}



<<解>>　21124

Project Euler(プロジェクトオイラー)Problem17。
同じC言語を使っても、いろいろな考え方ができるもんですね。

C言語でProject Euler 【Problem17】



☆応援お願いします☆

にほんブログ村