C言語でProject Euler(プロジェクト・オイラー)に挑戦 > スポンサー広告 > C言語でProject Euler 【Problem18】

    C言語でProject Euler(プロジェクト・オイラー)に挑戦 > Project Euler(プロジェクト・オイラー)【Problem16~Problem20】 > C言語でProject Euler 【Problem18】

    スポンサー広告

    スポンサーサイト

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

    Project Euler(プロジェクト・オイラー)【Problem16~Problem20】

    C言語でProject Euler 【Problem18】

    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言語





    ☆応援お願いします☆
    にほんブログ村 IT技術ブログ C/C++へ
    にほんブログ村


    <<C言語でProject Euler 【Problem12】C言語でProject Euler(プロジェクト・オイラー)に挑戦C言語でProject Euler 【Problem14】>>

    <<C言語でProject Euler 【Problem12】C言語でProject Euler(プロジェクト・オイラー)に挑戦C言語でProject Euler 【Problem14】>>

    コメント

    • No title
    • 25.シーフード
    • 2011年06月04日 |
    • 久々の更新ですねーー

      僕が作ってみたのもおいてみます

      他人のソースを見ると勉強になりますね・・・

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

      int strmax(int a, int b)
      {
      return a >= b ? a : b;
      }

      int main(void)
      {
      int str[15][15] = {
      {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, 4, 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 i, j;

      for(i = 13;i >= 0;i --)
      for(j = 13;j >= 0;j --)
      str[i][j] += strmax(str[i + 1][j], str[i + 1][j + 1]);

      printf("%d\n",str[0][0]);


      getch();
      return 0;
      }
    • [編集]
    • ありがとうございます!!
    • 26.CEuler
    • 2011年06月06日 |
    • すばらしい♪すごくすっきりですね・・
      人のを見せてもらうと、いかに自分の書いたコードが幼稚なのかとv-12
      本当に勉強になります。
      これからもいろいろ教えてください!!
      ありがとうございます。
    • [編集]

    コメントする

    トラックバック


    この記事にトラックバックする(FC2ブログユーザー)

    カテゴリ

    最新記事

    WiMAX & WiFi & モバイル

    便利ソフトいろいろ

    最新トラックバック

    最新コメント

    カウンター

    BlogRancking



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