C言語なら俺に聞け 146

2018/04/30(月) 04:47:37.50

C言語の話題のみ取り扱います C++の話題はC++スレへ
質問には最低限の情報(ソース/コンパイラ/OS)を付ける
数行で収まらないソースは以下を適当に使ってURLを晒す
https://paiza.io/
https://ideone.com/
http://codepad.org/

C11
http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1570.pdf

C99
http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf
http://kikakurui.com/x3/X3010-2003-01.html

C FAQ 日本語訳
http://www.kouno.jp/home/c_faq/

JPCERT C コーディングスタンダード
https://www.jpcert.or.jp/sc-rules/

前
C言語なら俺に聞け 144
https://mevius.5ch.net/test/read.cgi/tech/1514025223/

次スレを立てる時は本文の1行目に以下を追加して下さい
!extend:on:vvvvv:1000:512
-
※前スレ
C言語なら俺に聞け 145
http://mevius.5ch.net/test/read.cgi/tech/1519046038/

VIPQ2_EXTDAT: default:vvvvv:1000:512:----: EXT was configured

2018/08/04(土) 22:03:24.81

ﾗﾝﾀﾞﾑな値使ってるのに
まず最悪値になりようがない

だからな最悪値になるﾃﾞｰﾀ作ってみろよ

2018/08/04(土) 22:05:26.79

修正したら速くなっちゃった
https://ideone.com/yWEbrv

0.01262593秒

2018/08/04(土) 22:06:09.00

知恵遅れはﾗﾝﾀﾞﾑの値といってるから
入力値に疑似乱数使ってると思ってるかもしれないが
そもそもﾋﾟﾎﾞｯﾄの選択がﾗﾝﾀﾞﾑという意味だからな

2018/08/04(土) 22:06:54.29

「最悪値」って確率は関係ないから
文字通り「最悪値」

2018/08/04(土) 22:07:29.19

だからな30万件抽出できるｺｰﾄﾞ書いてみ

2018/08/04(土) 22:09:41.04

--普通の人のコード--
高速
コードサイズ小
1回スキャン
非破壊

--半角君のコード--
低速 (典型例で４倍の時間、最悪値は特にひどい)
コードサイズ大
複数回スキャン
破壊

2018/08/04(土) 22:12:28.07

0.01秒ｵｰﾀﾞｰが4倍とか議論不要なﾚﾍﾞﾙだからな

そもそも知恵遅れが書いたｺｰﾄﾞは条件が少しかわるだけで
待ってても結果が戻ってこないからな

2018/08/04(土) 22:13:07.54

データふやして比較しよう

2018/08/04(土) 22:15:28.18

>>734
恥の上塗りwww
お前の負けwww

2018/08/04(土) 22:16:12.21

知恵遅れの精神的勝利きたわ。。。

2018/08/04(土) 22:45:56.56

半角また負けたのか…

2018/08/04(土) 22:47:55.10

ｵﾚのｴﾚｶﾞﾝﾄなｺｰﾄﾞには勝てない
要素数,抽出数,ｴﾚｶﾞﾝﾄ(sec),ｱﾎ(sec)
10000,300,0.0000,0.0040
20000,600,0.0000,0.0150
30000,900,0.0000,0.0330
40000,1200,0.0000,0.0590
50000,1500,0.0000,0.0920
60000,1800,0.0010,0.1330
70000,2100,0.0000,0.1760
80000,2400,0.0010,0.2300
90000,2700,0.0010,0.2920
100000,3000,0.0020,0.3620
110000,3300,0.0020,0.4360
120000,3600,0.0020,0.5300
130000,3900,0.0020,0.6080
140000,4200,0.0020,0.7030
150000,4500,0.0030,0.8170
160000,4800,0.0020,0.9260
170000,5100,0.0020,1.0470
180000,5400,0.0020,1.1740
190000,5700,0.0030,1.3080
200000,6000,0.0020,1.4490
210000,6300,0.0020,1.5970
220000,6600,0.0020,1.7690
230000,6900,0.0020,1.9170
240000,7200,0.0030,2.0870
250000,7500,0.0030,2.2660
260000,7800,0.0050,2.4590
270000,8100,0.0040,2.6380
280000,8400,0.0020,2.8350
290000,8700,0.0010,3.0500
300000,9000,0.0020,3.2750

2018/08/04(土) 23:17:38.19

やっと処理が終わった
ｱﾎのｺｰﾄﾞのせいでCPUが熱くなったわ
数10万件ﾚﾍﾞﾙでｺﾚだからな

↓処理結果
http://fast-uploader.com/file/7088947692690/

一部抜粋
950000,28500,0.0140,33.5910
960000,28800,0.0100,33.4880
970000,29100,0.0190,34.1070
980000,29400,0.0080,34.8320
990000,29700,0.0100,35.4970
1000000,30000,0.0080,36.5600

↓ｸﾞﾗﾌ
https://i.imgur.com/nr9h0pH.png

知恵遅れ息してない

2018/08/04(土) 23:21:13.53

いつまでこの話続けるの？
専用スレ立てたら？

2018/08/05(日) 00:06:32.62

>>740
元の課題を書き換えて勝利宣言とか流石に恥ずかしすぎて真似できんわ

2018/08/05(日) 01:04:35.95

>>741
休日丸一日張り付いてるとこ見ると、他にやることないみたいだし、多分まだ続くで

2018/08/05(日) 01:45:43.20

上位３件で比較したらどうなるん？

**683** (ﾜｯﾁｮｲ a39f-Xflc) · 2018/08/05(日) 05:43:14.02

>>697
俺は半角君ではないが、あれの場合も2ヵ所じゃないか?
初期化含めると3か所か。

2018/08/05(日) 05:49:42.07

>>706>>713
まあ、他の言語使えばいいだけだな。
最終的なコードは同じになるだろう。それを自動でやるかプログラマが作るかの違いしかない。
C++も初期の頃はC言語へのコンバータだったしな。

2018/08/05(日) 07:52:08.09

>>745
#define
構造体
関数２個
計４か所

修正面倒
実際の半角君のコードもそんな面倒なコードにはなってない

2018/08/05(日) 07:56:35.30

暗澹として気持ちになる
半角君の言い分にも理はある
顧客がどういう方向にものごとを拡張したいと言い出すかなんてわからないんだ

なんでいりもしないくそコード増やしてんだと罵ることもできるし
これをスケーラビリティのある優れたコードだといって、もう一方クソ呼ばわりすることもできる
でも、書いたコードが結局どう評価されるかは将来を見通す能力で決まるんじゃない

顧客がこっちの様子みて事後的にきめてるんだ

2018/08/05(日) 08:03:17.72

>>673

2018/08/05(日) 08:09:08.23

>>699のコードにエラー時の処理を入れるのに
いちいち>>642にするのか？

使い分け
gotoの使いどころでは使う

2018/08/05(日) 08:17:28.22

多重ループを抜けるのに
半角君はどう書くつもりたろうか

switch / case からループを抜ける
これも良くあるコード

2018/08/05(日) 08:34:00.38

ループの中を関数化したうえで case 句からは return で即脱出するのかな
勝手な想像だけど

2018/08/05(日) 08:56:17.59

ここ喧嘩ばっかだから他所行くかーと思ってC++スレ行ったらそこでも喧嘩しててワロタ

2018/08/05(日) 08:57:44.72

一緒にすんな失礼な

　　　発　者　同　　　　　　　　 .　｡_　　 ____　　　　　　　　　　争
　生　同　.じ　　　　 .　　　　/´ 　 (ゝ___)　　　　　　　　　　い
　.し　士　.レ　　　　　　.__／'r-┴<ゝi,,ノ　　ro､　　　　　　は、
　.な　で　.ベ　　　　 ∠ゝ　(ゝ.／/｀　　 ./｀　 }⌒j　　　　　
　.い　し　.ル　　　　　　　} ⌒ ／｀ヽ､_∠l,ノ　・ヽ´
　.! !　か　の　　　　　　 /　　´..:.} ＞､､___,　 .r､ｿ､｀＼
　　　　　　　　　　　　　/　　　..:.:.}　　　/　　　∨　｀￣
　　　　　　　　　　　／　　　..:.:./　　　　　　丶
　　　　　　　　　　 /　＿､　..:.:.:.{　　　 .{.:.:.　　　＼
　　　　　　　　　　{　　　..:Y　　.ゝ､　　 {.:.:.:.:.　　　ヽ
　　　　　　　　　　､　　..:/　丿　.:〉　　 >.- ⌒ 　. 　ヽ
　　　　　　　　　 / {.　..:./　ｿ　..:./　 .(　　　　..:.:.:｀　..:}
　　　　　　　　 ./..:.:}.:.:./ ヘ､ ..:./　　 .＼　..:.:r＿,ノ､.:.:}
　　　　　　　　./..:.:/.:/　　 {.:./　　　　　X.:.:}.}　　 X X
　　　　　　　 /..:.:/ .}.: 　　 }:/ 　　　　　　.Y丶ヽ　　Y.:Y
　　.　＿＿／.:／　{　}　　《.〈､　　　　＿,,__>.:》丶　 Y.:＼
　　／.:.:.:.:.::／　　 !.:.:ゝ　　ゝ.:.￣ヾ　´:.:.:.:.:.:.:.:.:ヾゝ　　＼.:￣＞

2018/08/05(日) 10:50:56.85

というかだ
randとquickselectどっからコピペしてきたのか正直にいいなさい

非の打ちどころなく最適化されたロジック
筋のいい関数分割
的確な規約にのっとった命名
正確な英語

おまえがつくったのbakaとallocとfree_dataだけだろ
関数ごとにあまりにも作成者の知性差がありすぎる

2018/08/05(日) 10:53:47.86

partitionの中はそうでもないか

2018/08/05(日) 10:57:17.82

質問者そっちのけで
議論だけは続きます
いつものパターン

2018/08/05(日) 11:03:06.42

問題は解決してるじゃない

2018/08/05(日) 11:15:46.84

そもそもどれが質問だったかわからない

2018/08/05(日) 11:25:14.55

何を議論しているのかも誰も分からない

2018/08/05(日) 11:25:39.76

https://ideone.com/H6J9g6
ｺﾚで上位3件と
ｺﾚで上位3%の比較ができる

ちなみにｱﾎのｺｰﾄﾞが混じってるせいでWebでは動かない

https://en.wikipedia.org/wiki/Quickselect
ちなみにｺｰﾄﾞはｺﾚみながらちゃんとｵﾚが作ったからな

あとな　quickselect　は見直してたら一箇所ｺｰﾄﾞに誤りがあったわ

動作自体に大きな影響はない
それがなんでかは、それでどう動作がかわわるか、それがどういう修正なのかは
きっとこのｽﾚの知恵遅れたちには分からない

疑似乱数生成器は普通にxorshiftｺﾋﾟって作ったわ
あれならｲﾝﾀｰﾈｯﾂにいるようなどんなﾊﾞｶが書いても同じ結果になるからな
その部分だけはあってるわ

で、あとは、ﾃｽﾄ評価用関数の名前がどうこうしかないﾜｹか
まあｵﾂﾑの程度がよくしれるわ

2018/08/05(日) 11:51:24.52

1個も自分で考えたアルゴリズムが無いっていう
選択も正しくない

2018/08/05(日) 11:54:12.46

ﾊﾝｶｸ君「100件から上位3件のｿｰﾄじゃダメだ!
　　　　100万件から上位3万件を抽出（未ｿｰﾄ）できるｸｲｯｸｾﾚｸﾄがｴﾚｶﾞﾝﾄ！」

全角君「１億件をソートするにはそれじゃダメだろ　ヴォケが！
　　　　『マルチコアの並列ソート』こそがグレイシャス！」

二　倍　角　君　「　ダ　ァ　ホ　が　！　　１　０　０　億　じ　ゃ　！
　　　　　　　　　　量　子　C　P　U　で　超　並　列　じ　ゃ　ー　い　！　！」

今後の展開を想像したらわくわくしてきた
にしても　今日もあっついなぁ……

2018/08/05(日) 11:56:40.45

元は100個だか1000個だかだよ確か

2018/08/05(日) 12:05:44.10

なんかしょうもない争いしてんのな
どんぐりの背比べ

2018/08/05(日) 12:19:17.66

病気の発作みたいなもの
しばらく放置して、本人が落ち着くのを待つ
かまえばかまうほど、病気は進行する

2018/08/05(日) 12:25:21.31

またCPUが熱くなったわ
今回はvmwareで動作してるLinuxで動作させた

↓処理結果
http://fast-uploader.com/file/7088994902722/

　上位3件
　https://i.imgur.com/cBCyXmq.png
　上位3%
　https://i.imgur.com/SxxNkoj.png

もうねｵﾚのｺｰﾄﾞがｴﾚｶﾞﾝﾄすぎて困るわ
ｷﾐﾗとはﾚﾍﾞﾙが違うﾜｹ　ﾚﾍﾞﾙが
ｷﾐﾗとはｽﾃｰｼﾞが違うﾜｹ　ｽﾃｰｼﾞが

分かった？

2018/08/05(日) 12:30:52.32

よほどくやしかったんだろうね

2018/08/05(日) 12:35:47.77

あとな、知恵遅れが自分で新しいｱﾙｺﾞﾘｽﾞﾑを考えるとか
1億年たってもﾑﾘだからな

ｵﾚﾚﾍﾞﾙの人間ぐらいにならないとﾑﾘ

このｽﾚにいるような知恵遅れを遥かに凌駕する先人が
考えたｱﾙｺﾞﾘｽﾞﾑすら使いこなせてない

はっきりいってな低学歴知恵遅れやｸｿﾆｰﾄは
自己評価が高すぎるﾜｹ
低学歴知恵遅れやｸｿﾆｰﾄは自分のｶｽっぷりの自覚がない
まずｺｺが問題なﾜｹ

そんな知恵遅れが新しいｱﾙｺﾞﾘｽﾞﾑとかな逆立ちしてもﾑﾘだからな
知恵遅れや凡人はまず適切なｱﾙｺﾞﾘｽﾞﾑを選択できるようになるのが先だからな

2018/08/05(日) 12:37:41.32

日本ではPGは低学歴底辺しかならない職業だからな
しょうがないという側面もなある

おのずと低学歴底辺の頭悪いのばっかりになる

2018/08/05(日) 12:43:27.32

長文で自己紹介乙

2018/08/05(日) 12:57:32.94

まちがいがあったんだろうか？
相手が間違ってるかもしれないのに知ったげして

2018/08/05(日) 13:07:24.80

いつもいってることだが
ﾚｽしてるﾔﾂが低学歴か
ﾚｽしてるﾔﾂがﾆｰﾄかなんかな
ﾚｽみればすぐに分かることだからな

残念なことにそれをいくら隠そうとしても
隠すことはできない

本人はﾊﾞﾚてないつもりかもしれないが
ﾁｮﾝﾊﾞﾚなﾜｹ

2018/08/05(日) 13:12:35.48

お前の書き込みが病的だからお前が特定されてるだけだろ
ほかのやつの学歴なんか一切わからんわｗ

2018/08/05(日) 13:22:37.54

#include <stdio.h>

int func(int n)
{
if(n==0)
return 0;
if(n==1)
return 1;
return(func(n-2)+func(n-1));

}

int main()
{
printf ("%d",func(4));

return 0;
}

これの出力は３なんだけど

これ、永久的数が増えていく気がするんだけど。。。
どういう考え方で3になるか教えてほしい

2018/08/05(日) 13:28:13.17

4
2, 3
0, 1, 1, 2
0, 1, 1, 0, 1

2018/08/05(日) 13:29:48.92

>>776
足し算の合計としてじゃなく２つのfuncとして返されるってこと？
そしてその連続ってこと？

2018/08/05(日) 13:31:08.57

>>775
フィボナッチだってことは解ってる?
https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0

func(0) = 0
func(1) = 1
func(2) = func(0) + func(1) = 0 + 1 = 1
func(3) = func(1) + func(2) = 1 + 1 = 2
func(4) = func(2) + func(3) = 1 + 2 = 3

2018/08/05(日) 13:41:13.29

>>778
え、概念はわかった
func(0) = 0
func(1) = 1 ってどこからわかるんだ？
returnではないよね？

2018/08/05(日) 13:43:51.70

return 0;ってはっきり書いてあるやろ

2018/08/05(日) 13:45:55.07

>>780
え、リターンって　定型文というか終わりを意味するだけだと思ってた。

2018/08/05(日) 13:52:07.99

#include <stdio.h>
int func(int n, int stack)
{
++stack;
if(n==0) {
for (int i = 0; i < stack; ++i) printf(" ");
printf("[%d] returned func(%d) -> %d\n", stack, n, 0);
return 0;
}
if(n==1) {
for (int i = 0; i < stack; ++i) printf(" ");
printf("[%d] returned func(%d) -> %d\n", stack, n, 1);
return 1;
}
int i_ret = func(n-2, stack) + func(n-1, stack);
for (int i = 0; i < stack; ++i) printf(" ");
printf("[%d] returned func(%d) + func(%d) -> %d\n", stack, n - 2, n - 1, i_ret);
return(i_ret);
}

int main()
{
printf ("%d",func(4, 0));
return 0;
}

このｽﾚの知恵遅れがどうこういうだけﾑﾀﾞ
ｺﾚ動かして自分で考えればﾊﾞｶでもﾁｮﾝでも分かる

2018/08/05(日) 13:57:48.29

>>781
return は関数を抜けて　呼び出し元に戻り値を返すんだよ

2018/08/05(日) 14:15:22.97

>>781
なぜ、そんなものが存在するのか
つまり、必要なのか
ただブレースを閉じるだけではダメなのか
疑問を持ったことはないのか？

2018/08/05(日) 14:56:39.59

https://ideone.com/lYgehQ

ｺﾚでfuncが再帰による深さ優先探索が行われてる様子も分かるﾊｽﾞ
ｺｺまで分かるならこの部分の課題は終わりのﾊｽﾞだ

2018/08/05(日) 16:39:28.00

ヒープソートの参照のみならオーダー（計算量）はどうなるか。
先着順
当てたらアマギフ

2018/08/05(日) 16:43:08.34

ダニング＝クルーガー効果か。こういうのも既に研究されているんだな。
https://ja.wikipedia.org/wiki/%E3%83%80%E3%83%8B%E3%83%B3%E3%82%B0%EF%BC%9D%E3%82%AF%E3%83%AB%E3%83%BC%E3%82%AC%E3%83%BC%E5%8A%B9%E6%9E%9C

2018/08/06(月) 01:43:03.72

低能事件に続き5chでも半角事件が来るのか？

2018/08/06(月) 17:48:10.34

俺も何度かここで質問してるが、ム板にしては答えちゃんと返してくれるスレなんだよ。
ただただ質問者と回答者以外の第三者の介入が必ず発生して荒れ出すだけで・・・ｗ

2018/08/06(月) 20:11:30.49

>>785
なんでindent() のforの++iってなんか意味あるの？

2018/08/06(月) 20:12:03.76

2ch慣れというか5ch慣れしてスルーカパワーが高まった人でないと中々難しいのかも知れんのう

2018/08/06(月) 22:34:10.82

一番上と内部でレベルが合ってるように見えてて実はズレてる気持ち悪さ
中に入れるか呼び出し場所で外に書くかどっちかにしる

2018/08/06(月) 23:08:00.95

あとひどいのがprintしてる"return"の後ろの文字列の示すところが変わってること
固定値返してるところでfunc(n) -> n みたいにさらに下位を呼び出してるみたいにとれる書き方がしてあって
return func(2-2) + func(2-1) -> 1 とか計算内容を書いてるところと一貫性がとれてない

2018/08/06(月) 23:12:24.56

でも計算内容を展開してるだけだからいいっちゃいいのか
うーん

2018/08/06(月) 23:39:21.68

全然ずれてない
ｺｰﾙｽﾀｯｸの深さとぴったり一致してる

ｵﾂﾑが足りない知恵遅れのために
さらにﾑﾀﾞな補助出力をつけてやったぞ（AとB）

　https://ideone.com/2vP2kN

ここまでくると
ﾒｸﾗやﾂﾝﾎﾞを誘導するのに近い。。。

　↓この課題は、最終的には、ｺﾚにおちつくことになる
　　（なんでかは、nを増やせばきっと知恵遅れでも分かるとは思ってたからな）
　https://ideone.com/eaJEjX

補助出力がないとなにやってるのかすら分からないﾒｸﾗやﾂﾝﾎﾞでは
ｺﾚがなにやってるかもきっと理解できないわ
u_l、u_r、u_yしかないからな

知恵遅れは再帰が理解できてないのが、よおく分かったわ

2018/08/06(月) 23:51:48.07

余計紛らわしくなっとるわ！同じレベルで連続でリターンすんなしｗ
関数の戻りと呼び出し先の戻りがごちゃごちゃに

2018/08/07(火) 00:04:14.76

https://ideone.com/2vP2kN

知恵遅れ対応はｺﾚが限界

2018/08/07(火) 00:19:28.13

とてもわかりよいです

2018/08/07(火) 00:21:00.39

フィボナッチごときでよくもまあ話題が続くねえ

2018/08/07(火) 00:22:04.86

一般項の求め方くらい学校で習わなかった？

2018/08/07(火) 12:37:07.91

記憶から消滅

2018/08/07(火) 12:49:11.36

一般項は実数を扱うせいで誤差が出るから論外

2018/08/07(火) 12:50:36.34

誤差www
そりゃアホが作れば誤差が問題になるだろうねえwww

2018/08/07(火) 12:51:27.81

アホは素直に加算を繰り返せば良いよ

2018/08/07(火) 17:18:17.21

あれ？今日は半角にしないんだ。

2018/08/07(火) 19:11:24.43

おれは半角野郎じゃない
半角野郎はアホだから無理

◆QZaw55cn4c (ﾜｯﾁｮｲ 7f60-0Uuo) · 2018/08/07(火) 19:21:21.20

>>802
√5 の係数を整数で持てばいいのでは？
F_n = （φ^n - (-φ)^(-n)) / √5, φ=(1 + √5)/2

2018/08/07(火) 20:18:00.72

富士山麓オウム啼く・・・あれ？怖いなこれ

2018/08/07(火) 22:59:36.12

https://ideone.com/jzecIF

やはり
整数を足すにかぎるわ

2018/08/07(火) 23:08:45.73

IEEEの倍精度（64bit）で15～16桁程度の精度
つまりdouble、>>809の精度が概ねその程度

64bit整数なら19桁はいける

2018/08/07(火) 23:43:22.81

相変わらずアホだね
視野が狭い

2018/08/07(火) 23:47:20.78

ルートとｎ乗求める処理オーダーってどんなんじゃろ

６４bitまでならルート使ったほうが早いだろうけど
結局桁数が大きくなったらルートとってｎ乗してって結構処理重そう

じつは全部足し算したほうが早かったりして

2018/08/08(水) 05:09:15.02

重いのはべき乗のほうだね

2018/08/08(水) 07:15:16.24

nが大きい場合の計算オーダー

足し算の繰り返しの場合 : n^2
一般項を普通に計算した場合 : n (log n)^2

2018/08/08(水) 09:01:38.18

足し算の繰り返し：O(n)
一般項：O(1)
じゃないの？

2018/08/08(水) 12:44:41.36

加算、乗算、expなどの計算がO(1)で出来る範囲ならそうだね

2018/08/08(水) 12:50:59.40

>>816
まずはO(1)の定義を調べようか…

2018/08/08(水) 12:52:04.40

お前より詳しいと思うよ

2018/08/08(水) 15:07:25.41

お前のほうが可愛いよ

2018/08/08(水) 16:09:12.75

ありがと

2018/08/08(水) 18:58:28.93

フィボナッチの私の回答

nが比較的小さな数までである場合、テーブルを持つのが最速であることは間違いない

じゃあテーブルを持たない場合、

固定有効精度であれば、以下で求めるのが計算量のオーダーが1
(int)(exp(.4812118250596034475*n-.8047189562170501873)+0.5)

floatやdoubleではなく、4倍精度や100倍精度であってもオーダーは1
上の2個の定数は事前に計算しておけばいいし、
毎回計算してもnとは無関係
nが非常に小さい数でなければ単純に加算するよりは上記の方が速いでしょう
floatやdoubleであれば1行で済みます

2018/08/08(水) 19:03:59.97

じゃあ多倍長演算を用いて任意のnに対して正確に求める場合を考える

以下は基礎知識
n番目のフィボナッチ数の桁数はnに比例する
乗算の計算オーダーは、桁数をnとすると n log(n)
ルートの計算オーダーは n log(n)
n乗は、オーダーlog(n)回の乗算で求まる

以上より、一般項の式の通りまじめに計算しても
オーダー n (log n)^2 で計算できる

2018/08/08(水) 19:10:00.90

工夫すると、計算オーダーを n log n にすることが出来る

行列の形でフィボナッチ数列の漸化式を記述すると
|0 1|^n |0|
|1 1| . . |1|
でn番目とn+1番目のフィボナッチ数が求まることがわかる

この式を用いれば
計算オーダー n log n で正確に n 番目のフィボナッチ数を求めることができる

◆QZaw55cn4c (ﾜｯﾁｮｲ 7f60-0Uuo) · 2018/08/08(水) 19:13:46.21

>>810,812,814
漸化式 f(n+2)=f(n+1)+f(n) から一般のf(n) を求めるオーダーはΟ(n)
一般式 >>807 から求めるオーダーはΟ(log n)
だと思う
https://mevius.5ch.net/test/read.cgi/tech/1434079972/49
c を定数として、c^n を求めるにはΟ(log n) でいける

2018/08/08(水) 19:30:35.51

元は>>775の初心者の質問で
計算オーダーとか全く関係なかったんだけど
半角君があまりに無知な癖に自信過剰なので
つい書いてしまった

2018/08/08(水) 19:34:04.93

>>824
それは固定有効精度の場合

固定有効精度であればオーダーは1で計算出来る
>>821参照

2018/08/08(水) 19:36:02.18

固定精度であれば
四則演算もexpも丸めも全て
値によらず固定時間で計算出来る