プログラミングのお題スレ Part12

**デフォルトの名無しさん** · 2018/09/28(金) 10:09:07.13

プログラミングのお題スレです。

【出題と回答例】
1 名前：デフォルトの名無しさん
　　お題：お題本文

2 名前：デフォルトの名無しさん
　　>>1 使用言語
　　回答本文

【ソースコードが長くなったら】 (オンラインでコードを実行できる)
https://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
https://runnable.com/
https://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/

宿題は宿題スレがあるのでそちらへ。

前スレ
プログラミングのお題スレ Part10
https://mevius.5ch.net/test/read.cgi/tech/1514772904/

プログラミングのお題スレ Part11
https://mevius.5ch.net/test/read.cgi/tech/1524570314/

**デフォルトの名無しさん** · 2018/09/28(金) 10:41:53.02

console.log('>>%d乙', 1);

**デフォルトの名無しさん** · 2018/09/28(金) 10:55:48.49

3つの値の最小値を調べるには2回比較をしなくてはならないことを証明せよ

**デフォルトの名無しさん** · 2018/09/28(金) 12:28:47.83

やだ

**デフォルトの名無しさん** · 2018/09/28(金) 13:55:38.90

>>3
3つの値のうちの最小値が分かった時の情報量はlog3
1回の比較によって得られる情報量はlog2
2回の比較で2log2=log4
log2<log3<log4なので最低2回の比較をしなければ最小値を知る事はできない

**デフォルトの名無しさん** · 2018/09/28(金) 14:20:38.29

>>3
回数の定義による
ハードウェアでパラにやれば1回だと言い張ることもできるし

**デフォルトの名無しさん** · 2018/09/28(金) 14:26:10.16

ここは数学のお題を解くスレではなくプログラミングのお題スレなので証明せよというお題ならば証明をするプログラムを作れという意味になる。
決して人間が頭で考えて証明してはならない。

**デフォルトの名無しさん** · 2018/09/28(金) 14:46:03.56

3つの数単体同士の比較だけじゃなくて、a+bとcとかa^cとb+cとか無限に考えられるから有限時間で証明するのは無理では？

**デフォルトの名無しさん** · 2018/09/28(金) 21:22:39.80

ID:jm6QTuW3

**デフォルトの名無しさん** · 2018/09/28(金) 22:47:33.75

[a, b, c].min

**デフォルトの名無しさん** · 2018/09/28(金) 23:21:12.89

>>8
値と言ってるのにどこから数式が出てくるんだろう…

**デフォルトの名無しさん** · 2018/09/28(金) 23:31:28.87

例えばR^3の関数f(x, y, z)で
xが最小の時負、xが最小でなくyが最小の時0、xかyが最小でなくzが最小の時正
になるC^∞級の関数は存在するのでこの関数を使えば比較は1回で済む

**デフォルトの名無しさん** · 2018/09/29(土) 00:17:28.49

>>12
例えばどんな関数？

**デフォルトの名無しさん** · 2018/09/29(土) 01:00:25.54

比較って値そのものの大小の比較ってとだろ

**デフォルトの名無しさん** · 2018/09/29(土) 01:06:03.17

比較というのは差をみつけることだからな
ｺｺでの差は引き算の差の意味ではない、当然

数字を引き算して差を求めることもできる、当然

**デフォルトの名無しさん** · 2018/09/29(土) 01:15:28.45

>>3が言ってる比較って値そのものの差による比較ってことだろ

ってことな
わかった？

**デフォルトの名無しさん** · 2018/10/01(月) 20:03:33.29

お題：f(n)::={nを連続するいくつかの正整数の和として表す表し方の総数}とおく
例えば、15=7+8=4+5+6=1+2+3+4+5よりf(15)=4である
上限Nが与えられたとき、n<=Nでf(n)が奇数となるようなnをすべて足し合わせた値を求めよ

10 -> 24
100 -> 665
1000 -> 18006
10000 -> 571940
100000 -> 18010994
1000000 -> 569929080
10000000 -> 18001029437
100000000 -> 569128815672
1000000000 -> 17994029079715

**デフォルトの名無しさん** · 2018/10/01(月) 20:21:00.27

> nを連続するいくつかの正整数の和として表す表し方の総数

15は7+8と4+5+6と1+2+3+4+5の3通りの表し方があって
その総数f(15)が4ってどういうこと？

**デフォルトの名無しさん** · 2018/10/01(月) 20:26:01.73

>>18
自身も含まれるんじゃない？

**デフォルトの名無しさん** · 2018/10/01(月) 21:52:20.39

>>17 Java
https://ideone.com/FqcPpb
適当に作ったが考え方を変えないとideone時間が足りない

**デフォルトの名無しさん** · 2018/10/01(月) 22:05:00.23

>>17
>連続するいくつかの正整数の和として表す表し方の総数

http://izumi-math.jp/sanae/MathTopic/renzokuwa/renzokuwa.htm
>1以外の奇数の約数と同じだけある

ttps://www.eikoh-seminar.com/echtas/blog/2015/10/post-224.html
>１以外の奇数の約数を何個持っているか

**デフォルトの名無しさん** · 2018/10/01(月) 23:56:46.25

>>17 Java
https://ideone.com/z2q0Sj

>>21の考え方を導入してみた

**デフォルトの名無しさん** · 2018/10/02(火) 20:12:32.93

>>17 Java
https://ideone.com/m7oieG
BitSetなんて使わず普通に再帰使ったほうが早かった…