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

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

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

2回答

1793閲覧

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

apeirogon0813

総合スコア117

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

0グッド

0クリップ

投稿2018/10/18 09:24

編集2018/10/18 10:24

フィボナッチ数列とは,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が大きくなってしまうと誤った結果を吐き出してしまいます。

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

C言語

1include<stdio.h> 2int number = 0; 3 4struct golden { 5 long long int a; 6 long long int b; 7}; 8 9struct golden mult_golden(struct golden x, struct golden y) { 10 number += 1; 11 struct golden z; 12 z.a = (((x.a % 2018) * (y.a % 2018)) % 2018 + ((x.b % 2018) * (y.b % 2018)) %\ 13 2018) % 2018; 14 z.b = (((x.a % 2018) * (y.b % 2018)) % 2018 + ((x.b % 2018) * (y.a % 2018)) %\ 15 2018 + ((x.b % 2018) * (y.b % 2018)) % 2018) % 2018; 16 return z; 17} 18 19struct golden power_golden(struct golden x, int n) { 20 struct golden z; 21 22 if(n == 0) { 23 z.a = 1; 24 z.b = 0; 25 return z; 26 } else if(n % 2 == 0) { 27 z = power_golden(x, n/2); 28 return mult_golden(z, z); 29 } else { 30 z = power_golden(x, n-1); 31 return mult_golden(z, x); 32 } 33} 34 35int main(void) 36{ 37 struct golden x = { 1, -1 }; 38 int i,n; 39 scanf("%d", &n); 40 x = power_golden(x, i); 41 printf("%lld\n", x.a); 42 43 return 0; 44} 45

気になる質問をクリップする

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

yohhoy

2018/10/18 10:15

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

2018/10/18 10:23

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

回答2

0

ベストアンサー

-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 09:30

編集2018/10/18 10:19
set0gut1

総合スコア2413

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

apeirogon0813

2018/10/18 10:32

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

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
より検算

C

1#include <stdio.h> 2#include <string.h> 3 4#define N (109) 5 6int main(void) 7{ 8 int arr[N + 1]; 9 memset(arr, 0, sizeof(arr)); 10 arr[0] = 0; 11 arr[1] = 1; 12 13 int n = 0, i = 0; 14 scanf("%d", &n); 15 n = n > N ? N : (n < 0 ? 0: n); 16 17 // 動的計画法・・・なのか 18 for(i = 2; i <= N; i++) { 19 arr[i] = (arr[i - 1] + arr[i - 2]) % 2018; 20 } 21 22 printf("%d\n", arr[n]); 23 24 return 0; 25}

投稿2018/10/18 09:57

rururu3

総合スコア5545

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

apeirogon0813

2018/10/18 10:11

よく理解していませんがこのコードで試してみたところ 大きい入力100000でも10000000でも1597と出力されてしまっています。
yohhoy

2018/10/18 10:17 編集

(勘違いコメントのため削除しました)
rururu3

2018/10/18 10:15

n は 109 以下の正の整数ということで100000でも10000000でも109として出してます。後は解答のとおりです。
rururu3

2018/10/18 10:21

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

2018/10/18 10:24

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

2018/10/18 10:36 編集

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問