質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.59%

フィボナッチ数列のn番目の剰余を求める時、値が大きくなってしまうと計算が正しく出力されません。

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 1,757

apeirogon0813

score 74

フィボナッチ数列とは,F0 = 0,F1 = 1,Fn = Fn−1 + Fn−2 (n ≥ 2) で定義される数列であり,以下の等
式が成り立つことを簡単に示せる:
(1 − φ)^(n−1) = Fn − Fn−1φ
この等式は,「(1 − φ)^(n−1) を a + b φ (a, b は整数) の形で表したときの a が Fn そのものである」という
ことを表している.この性質を利用します。

標準入力で与えられる整数 n に対し,フィボナッチ数列の n 番め Fn を 2018 で割った余りを標準出力に
出力するプログラムを作成せよ.ただし,n は 10^9 以下の正の整数であると仮定してよい.
入力例       出力例
10                  55
入力例            出力例
100               1705
入力例            出力例
1000000000    1997

なおn + m を d で割った余りは,「n を d で割った余り」と「m を d で割った余り」を足したものを d で
割った余りに等しい.
• n × m を d で割った余りは,「n を d で割った余り」と「m を d で割った余り」を掛けたものを d で
割った余りに等しい.

この問題で与えた入力nが大きくなってしまうと誤った結果を吐き出してしまいます。

おそらく値がマイナスのものに剰余を行ってしまっているからだと思うんですが、
改善方法が思い当たらないのでご教示願います。

include<stdio.h>
int number = 0;

struct golden {
  long long int a;
  long long int b;
};

struct golden mult_golden(struct golden x, struct golden y) {
  number += 1;
  struct golden z;
  z.a = (((x.a % 2018) * (y.a % 2018)) % 2018 + ((x.b % 2018) * (y.b % 2018)) %\
 2018) % 2018;
  z.b = (((x.a % 2018) * (y.b % 2018)) % 2018 + ((x.b % 2018) * (y.a % 2018)) %\
 2018 + ((x.b % 2018) * (y.b % 2018)) % 2018) % 2018;
  return z;
}

struct golden power_golden(struct golden x, int n) {
  struct golden z;

  if(n == 0) {
      z.a = 1;
      z.b = 0;
      return z;
    } else if(n % 2 == 0) {
   z =  power_golden(x, n/2);
    return mult_golden(z, z);
  } else {
   z = power_golden(x, n-1);
    return mult_golden(z, x);
  }
}

int main(void)
{
  struct golden x = { 1, -1 };
  int i,n;
  scanf("%d", &n);
  x = power_golden(x, i);
  printf("%lld\n", x.a);

  return 0;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • yohhoy

    2018/10/18 19:15

    「ただし,n は 109 以下の正の整数であると仮定してよい.」のに「入力例 1000000000」があるのは何故です?

    キャンセル

  • apeirogon0813

    2018/10/18 19:23

    すみません問題表記に誤りがありました。訂正します。n は 10^9 以下の正の整数であると仮定してよい

    キャンセル

回答 2

checkベストアンサー

+1

-1 % 2018 を -1 と答える言語と 2017 と答える言語があり、このへん混乱するところですね。
マイナスになってても剰余値として間違ってるってことはないので、適宜修正すれば良いです。
例えば次のようにすると想定通りの出力が得られるかと思います。

struct golden mult_golden(struct golden x, struct golden y) {
  // 前略 変更なし
  if (z.a < 0) z.a += 2018;
  if (z.b < 0) z.b += 2018;
  return z;
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/10/18 19:32

    なるほど。確かに剰余値は間違っていはいないですね。
    おかげさまで意図している出力を得ることができました。
    ありがとうございます。

    キャンセル

0

再起でやったら40ぐらいからとても遅いので配列で&大きな数になるからmod 2018で

※入力例        出力例
1000000000    1997
1997ではなく1597のはず
http://www.suguru.jp/Fibonacci/fib1-10000/fib1-1000.html
https://keisan.casio.jp/exec/system/1510710795
より検算

#include <stdio.h>
#include <string.h>

#define N (109)

int main(void)
{
    int arr[N + 1];
    memset(arr, 0, sizeof(arr));
    arr[0] = 0;
    arr[1] = 1;

    int n = 0, i = 0;
    scanf("%d", &n);
    n = n > N ? N : (n < 0 ? 0: n);

        // 動的計画法・・・なのか
    for(i = 2; i <= N; i++) {
        arr[i] = (arr[i - 1] + arr[i - 2]) % 2018;
    }

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

    return 0;
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/10/18 19:21

    検算で利用したサイトでF2=1なので
    F0=0, F1=1
    であってるかと(10と100であってることは確認してます)

    キャンセル

  • 2018/10/18 19:24

    申し訳ありません' ^ 'が抜けていました。正しくは10^9 以下の正の整数であると仮定してよいです。

    キャンセル

  • 2018/10/18 19:36 編集

    10億・・・これは再起では無理だ

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.59%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • トップ
  • Cに関する質問
  • フィボナッチ数列のn番目の剰余を求める時、値が大きくなってしまうと計算が正しく出力されません。