←検索窓の楽しみ方
  ショッピングモール  掲示板ランキング


掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板1

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧

No.4771

C言語でプログラムを作ってください
投稿者---gou(2005/10/25 10:56:25)


オイラー(Euler, 1707年-1783年)は、1769年頃に、「a5+b5+c5 +d5=e5を満足する正の整数はない」という予想を立てた。コンピュータを用いて、偉大な数学者であるオイラーの予想を覆せ。また、このプログラムは多少時間がかかることが予想されるので、効率よくプログラムを組むこと。そのため、すべてを計算すると大変なので、a<b<c<d<e<200を仮定してよい。

ヒント:
カウンタ変数を5つ用意して5重ループを構成する。ループ数が多くなるので計算量に注意されたい。 2005程度の値になると、通常のint型の表現範囲を超えるので注意すること。
答えは、次のとおり
a=27,b=84,c=110,d=133,e=144
a5=14348907,b5=4182119424,c5=16105100000,d5=41615795893,e5=61917364224
c5,d5,e5は、int型の表現範囲を超えているので、注意してください


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:C言語でプログラムを作ってください 4772 REE 2005/10/25 11:09:24
<子記事> Re:C言語でプログラムを作ってください 4773 たいちう 2005/10/25 14:33:01


No.4772

Re:C言語でプログラムを作ってください
投稿者---REE(2005/10/25 11:09:24)


【掲示板利用宣言】
課題の丸投げはしません。



この投稿にコメントする

削除パスワード

No.4773

Re:C言語でプログラムを作ってください
投稿者---たいちう(2005/10/25 14:33:01)


問題が面白かったのでヒントをあげます。

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
  TBigInteger = class
    High, Low: Integer;
  public
    constructor Create(N: Integer);
    function ToString: String;
    procedure Add(Big: TBigInteger);
    procedure Clear;
    function Equals(Big: TBigInteger): Boolean;
  end;

const
  MaxNumber = 200;
  Segment = 1000000;

procedure TBigInteger.Add(Big: TBigInteger);
var
  I: Integer;
begin
  Low := Low + Big.Low;
  I := Low div Segment;
  Low := Low mod Segment;
  High := High + Big.High + I;
end;

procedure TBigInteger.Clear;
begin
  Low := 0;
  High := 0;
end;

constructor TBigInteger.Create(N: Integer);
begin
  Low := N * N * N * N;
  if Low > Segment then begin
    High := Low div Segment;
    Low := Low mod Segment;
  end;
  Low := Low * N;
  High := High * N;
  if Low > Segment then begin
    High := High + Low div Segment;
    Low := Low mod Segment;
  end;
end;

function TBigInteger.Equals(Big: TBigInteger): Boolean;
begin
  Result := (Low = Big.Low) and (High = Big.High);
end;

var
  A, B, C, D, E, I: Integer;
  Fifth: array[1..MaxNumber] of TBigInteger;
  Sum: TBigInteger;
begin
  for I := 1 to MaxNumber do
    Fifth[I] := TBigInteger.Create(I);
  Sum := TBigInteger.Create(0);

  for A := 1 to MaxNumber do
    for B := A + 1 to MaxNumber do
      for C := B + 1 to MaxNumber do
        for D := C + 1 to MaxNumber do begin
          Sum.Clear;
          Sum.Add(Fifth[A]);
          Sum.Add(Fifth[B]);
          Sum.Add(Fifth[C]);
          Sum.Add(Fifth[D]);
          for E := D + 1 to MaxNumber do
            if Sum.Equals(Fifth[E]) then
              Writeln(Format('%d^5 + %d^5 + %d^5 + %d^5 = %d^5',
                             [A, B, C, D, E]));
        end;

  for I := 1 to MaxNumber do
    Fifth[I].Free;
  Sum.Free;

  // quit
  Writeln('End.');
  Readln;
end.



# 効率面を抜本的に改善することは可能だろうか?
# Addの引数を4つにして、mod や div の回数を減らす、
# というようなことは、直ぐに思いつくが。
# より良いアルゴリズムはあるのか?


この投稿にコメントする

削除パスワード

No.4774

Re:C言語でプログラムを作ってください
投稿者---しっぽ(2005/10/25 23:30:37)


># より良いアルゴリズムはあるのか?

5乗には、
power(j, 5) % 10 == j % 10;
が真となる性質があるので、これを利用して
for E
のループ回数を減らせるかもしれません。

# もしかしてオイラーがウィナーになる八百長?



この投稿にコメントする

削除パスワード

No.4775

Re:C言語でプログラムを作ってください
投稿者---かずま(2005/10/26 01:13:32)


> # 効率面を抜本的に改善することは可能だろうか?
TBigInteger を使わずに、Real を使ったほうが速いのでは?


さて、C で書いてみたのですが、Borland C++ 5.5.1 で不思議な現象に
遭遇しました。まず、プログラムは次の通りです。

#include <stdio.h>
#include <time.h>

void p(int i) { printf("%d ", i); fflush(stdout); }

int proc(void)
{
    int a, b, c, d, e;  double x, y, z, f[200];

    for (e = 1; e < 200; e++)
        f[e] = (double)e * e * e * e * e;
    for (e = 1; e < 200; e++)
        for (p(e), d = 1; d < e; d++)
            for (c = 1; c < d && (z = f[c] + f[d]) < f[e]; c++)
                for (b = 1; b < c && (y = f[b] + z) < f[e]; b++) {
                    for (a = 1; a < b && (x = f[a] + y) < f[e]; a++)
                        ;
                    if (x == f[e])
                        return !printf("\na=%d b=%d c=%d d=%d e=%d\n",
                            a, b, c, d, e);
                }
    return printf("not found\n");
}

int main(void)
{
    clock_t t = clock();
    proc();
    printf("%g\n", difftime(clock(), t) / CLOCKS_PER_SEC);
    return 0;
}

このプログラムで、main() を削除し、proc を main に置き換えると、実行時間
がなぜか 約2倍に増えるのです。gcc 3.3.3 では、そんなことはありません。
OS は、Windows 98SE または Windows XP です。
皆さんのところでも同じ現象が出るのでしょうか?



この投稿にコメントする

削除パスワード

No.4776

Re:C言語でプログラムを作ってください
投稿者---かずま(2005/10/26 11:34:42)


> このプログラムで、main() を削除し、proc を main に置き換えると、実行時間
> がなぜか 約2倍に増えるのです。gcc 3.3.3 では、そんなことはありません。
> OS は、Windows 98SE または Windows XP です。
> 皆さんのところでも同じ現象が出るのでしょうか?

Windows 2000, AMD Duron 700MHz, 640MB で実行したところ、この現象は
出ませんでした。

clock() の呼び出しで、状況が変わるのかと思って、main() の中の clock()
を含む 2行を削除しただけのものを試したところ、また新たに不思議な現象
が出ました。

1 2 3 4
a=1 b=1 c=2 d=3 e=4

という結果になるのです。
調べたところ、f[a] = 1, y = f[b] + f[c]+ f[c] = 276 のとき、
x = f[a] + y = +NAN となっているようです。

Windows XP SP2, Pentium III 2.8GHz, 512MB でも同じ現象が出ましたが、
Windows 98SE, Pentinum II 400MHz, 128MB だとこの現象が出ません。

Borland C++ 5.5.1 には浮動小数点に関する何らかの問題があるのでしょうか?



この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    記事検索    ログ    タグ一覧




掲示板提供:Real Integrity