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

1 ：デフォルトの名無しさん：2018/09/28(金) 10:09:07.13 ID:phwOkayR.net

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

【出題と回答例】
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/

957 ：デフォルトの名無しさん：2019/01/31(木) 22:25:01.31 ID:xJsSt9Re.net

Python では、機械学習などの周辺ライブラリ一式が揃っているから、使われる

Ruby では、ベクトル演算のNArray があって、
処理速度はOctave にも匹敵するけど、一式揃っていない

北大の湊教授が作った、ZDD はあるけど

958 ：デフォルトの名無しさん：2019/01/31(木) 22:46:32.84 ID:2IY59Hh/.net

scipy/scipy/special/cephes at master ・ scipy/scipy
ttps://github.com/scipy/scipy/tree/master/scipy/special/cephes

この辺り見てみるとフォートランとCがそのまま使われてる

scipy/_comb.pyx at master ・ scipy/scipy
ttps://github.com/scipy/scipy/blob/master/scipy/special/_comb.pyx

このあたりをそのまま書ければいい

959 ：デフォルトの名無しさん：2019/02/01(金) 04:58:43.05 ID:IMBPiIxm.net

お題
平方数かどうか判定する

960 ：デフォルトの名無しさん：2019/02/01(金) 10:08:25.26 ID:VdCPb4pG.net

C++

#include <iostream>
#include <limits>

template <typename T>
bool is_safely_multiplicable(T a, T b) {
if (b == 0) return true;
return a <= (std::numeric_limits<T>::max() / b);
}

uint64_t sqrt_int(uint64_t x) {
if (x == 0) return 0;
uint64_t a = 1, b = x, c;
while (b - a > 1) {
c = (b - a) / 2 + a;
if (is_safely_multiplicable(c, c) && x >= c * c) a = c;
else b = c;
}
return a;
}

bool is_square_number(uint64_t x) {
uint64_t rt_x = sqrt_int(x);
return rt_x * rt_x == x;
}

961 ：デフォルトの名無しさん：2019/02/01(金) 18:32:58.66 ID:iYm26gLc.net

>>959
Haskell

isSqr a = isSqr' a [n * n | n <- [0..a]]
where
isSqr' x (l:_) |(x == l) = True
isSqr' x (l:_) |(x < l) = False
isSqr' x (_:ls) = isSqr' x ls

962 ：デフォルトの名無しさん：2019/02/01(金) 20:32:42.61 ID:iYm26gLc.net

Python

def isSqr(x):
n = 0
a = 0
while x <= a:
if x == a:
return True
n += 1
a = n * n
return False

リスト内包表記だとすぐ落ちた。。。
Haskellより持たない。。。

963 ：デフォルトの名無しさん：2019/02/01(金) 21:10:55.66 ID:qFuZrTt3.net

これはいかに巨大数を高速判定するかだろ

964 ：デフォルトの名無しさん：2019/02/01(金) 21:19:45.40 ID:qFuZrTt3.net

目星はこれを荒く使えばつきそう


逆数と平方根を求める高次収束アルゴリズム
http://www.finetune.co.jp/~lyuka/technote/fract/sqrt.html

高速根号計算
http://takashiijiri.com/study/miscs/fastsqrt.html

965 ：デフォルトの名無しさん：2019/02/01(金) 22:13:46.18 ID:kNvVsHFY.net

https://code.i-harness.com/ja-jp/q/4829b

966 ：デフォルトの名無しさん：2019/02/01(金) 23:10:20.49 ID:iYm26gLc.net

>>963
m = ？
n = m * m

m=10の時nの1/10で、m=100だとnの1/100

探すべきmが高速で小さくなって行く。
大きな数になる程、0<=mなループの始まり求めるの無理ゲー。。。

967 ：デフォルトの名無しさん：2019/02/01(金) 23:12:44.04 ID:VdCPb4pG.net

ttps://ideone.com/xr1vcE

Newton-Raphson法ほど速くはないがせめてO(log(N))くらいで実装せにゃお題として出てくる意味がなかろう

968 ：デフォルトの名無しさん：2019/02/02(土) 00:09:40.70 ID:/6KX0oFw.net

>>959 Lua
function isSquare(n)
local a = 0
local i = 1
while a < n do
a = a + i
i = i + 2
end
return a == n
end
print(isSquare(100000))
print(isSquare(10000))

969 ：デフォルトの名無しさん：2019/02/02(土) 03:47:32.54 ID:i2SNxKFt.net

いっそsqrt 関数実装。
頭悪いんで数学的じゃない。
256以上入れるとフリーズするけど、その範囲なら精度抜群。
精度を1つ落とすと(range(15)の値を1つ減らすと)2桁くらい大きな数を入れてもフリーズしなくなる。

def sqrt(x):
i = 1
if x == 0:
return 0
while x >= (i * i):
if x / i == i:
return i
i += 1
i -= 1
a = 0.1
for j in range(15):
while x >= (i * i):
i += a
i -= a
a *= 0.1
return (i - a)

970 ：デフォルトの名無しさん：2019/02/02(土) 09:51:18.58 ID:/6KX0oFw.net

>>959 J
f =: = *: @ <. @ %:

971 ：デフォルトの名無しさん：2019/02/02(土) 13:18:27.64 ID:CwD+xRo8.net

平方数かどうかを高速に判定する方法 - hnwの日記
https://hnw.hatenablog.com/entry/20140503


GNU MPのmpz_perfect_square_p関数の実装
GNU MPのソースコードを確認してみたところ、次のような処理だとわかります。

引数nのmod 256を計算し、平方数ではない数を判定する
平方数のmod 256は44種類の値しか出現しないので、入力の82.8%は平方数でないと判定できる
同様に入力nのmod 9, 5, 7, 13, 17（64-bitシステムではmod 97も）を計算し、平方数ではない数を判定する
これにより入力の99.25%（64-bitシステムでは99.62%）について平方数でないと判定できる
最後に、平方根を計算して平方数かどうか確認する

平方数ではない数の多くを事前にふるい落とし、判定できなかった数だけ真面目に平方根を求める、という方針だとわかります。

もちろん、GNU MPの場合のmod pの選び方は多倍長整数演算ならではだと言えます。
mod 256はサイズNにかかわらずO(1)で計算できるので、最初に行うことで全体の高速化に貢献できます。

また、2ステップ目の計算も2^24-1 = 9 * 5 * 7 * 13 * 17 * ...であることを利用し、多倍長整数であっても比較的高速に計算できるような実装になっています。
10進整数でmod 9を求める場合に全部の桁を足し合わせてからmod 9しても同じ結果になるのと同様、
下位から24bit区切りの数を足し合わせてからmod 2^24-1を計算することで、元の数のmod 2^24-1が計算できるのです。

972 ：デフォルトの名無しさん：2019/02/02(土) 13:43:47.68 ID:OgiywF+Q.net

>>949
えぇ…

973 ：デフォルトの名無しさん：2019/02/02(土) 16:31:05.91 ID:9W2pTWu+.net

>>972 その心は？

974 ：デフォルトの名無しさん：2019/02/02(土) 16:42:03.23 ID:OgiywF+Q.net

>>970
えぇ…

の間違い。

975 ：デフォルトの名無しさん：2019/02/02(土) 17:31:46.69 ID:rEiZ26fd.net

本質的に高度な数学的知識が要求され
る問題は板違いかと

言語によっては、問題にジャストフィット
するライブラリが標準で添付されているとか
ライブラリ管理コミュニティを通じて
容易に入手できるとかあるかもしれないが
その場合は紹介程度に。

言語処理系の言語処理の為の機能提供
である場合を除いて多くは本質的に多言
語に対応しており〜言語用のライブラリと
いう表現は兎も角〜言語のライブラリと表
現すると曖昧で誤解を招きやすい表現
として嫌われる場合もありえることに注意。
（別言語で記述される場合もある）

976 ：デフォルトの名無しさん：2019/02/02(土) 17:36:46.77 ID:XgXX/tZQ.net

なんしたのきゅうに

977 ：デフォルトの名無しさん：2019/02/02(土) 17:57:26.00 ID:rEiZ26fd.net

セルフホスティング対応な言語でライブラリを
自前で構成しているもので、他言語に移植されて
いない独自の機能を持つものもあるかもしれない
し、もっと極端に言えば独自性の高いライブラリに
最適化された言語を自前で作ってそれで記述され
ているものもあるかもしれないけど一般的には入手
は容易ではないかも

978 ：デフォルトの名無しさん：2019/02/02(土) 19:52:10.51 ID:hDNgHqpo.net

じゃあさ、各々複数行の
a.txt と、b.txtを並べて表示して。

979 ：デフォルトの名無しさん：2019/02/02(土) 23:25:24.42 ID:g8xy/J6N.net

辺に沿って動くとき、AからBまでの最短経路はいくつあるか
　　　　　　　　　┏┳┳┳┓B
　　　　　　　　　┣╋╋╋┫
　　　　　　┏┳╋╋╋╋┫
┏┳┳┳╋╋╋╋╋┻┛
┣╋╋╋╋╋╋╋┫
┣╋╋╋╋╋╋╋┫
┣╋╋╋╋╋╋╋┛
┗┻┻┻┻┻┻┛
A

980 ：デフォルトの名無しさん：2019/02/03(日) 00:45:38.22 ID:UGH880J+.net

おねえさんがロボットになるやつかｗ

981 ：デフォルトの名無しさん：2019/02/03(日) 00:55:19.58 ID:UTpNqxd4.net

中学受験の算数の問題に経路を数える問題があるよな
つまり小学生でも手計算で解ける

982 ：デフォルトの名無しさん：2019/02/03(日) 00:57:22.00 ID:72eosYJ+.net

>>975 アホちゃうの？
プログラムというのは、問題解決のための言語であって、問題が解決できなければどんなに美しい言語でも存在価値はない。
最速で美しく問題解決にたどり着ける言語が一番。 言語そのものの美しさなんて二の次。

英語でも日本語でも何でも良い。 利用できるものは何でも利用すれば良い。 好き嫌い言ってる奴はアホ。
どんなに綺麗な国の言葉でも高等教育が自国語でできない国がほとんど、それは利用できる教材が自国語で書いたものがないから。
日本語だったら英語を知らなくてもノーベル賞が取れるだけの教材(ライブラリ)が揃ってる。

983 ：デフォルトの名無しさん：2019/02/03(日) 01:53:34.29 ID:wxxHWwaf.net

別に高度な数学が必要になることは構わないけど、数学だけで話が閉じちゃうような問題はつまらないとは思う。数学的に解を求める解法自体が主題で、コーディングはただその解法を(日本語、英語などの自然言語と同様に)とあるプログラミング言語で記述しただけのような。
もちろん数学に価値がないといっているのではなく、話のウェイトとしてプログラムである部分がほぼないのなら、その話、ここじゃなくてもいいじゃんと思うよ。

984 ：デフォルトの名無しさん：2019/02/03(日) 04:02:35.76 ID:JyP+XfGy.net

つまらない問題だと思ったら無視すればいいだけじゃないかな
その問題に対して回答する人がいるなら、回答者(と出題者)にとっては
つまらない問題ではないってことなんだろうし

985 ：デフォルトの名無しさん：2019/02/03(日) 04:46:34.72 ID:1lu6X4vo.net

>>982
ＯＳ記述の言語は言語じゃないのか？
コンパイラなどの言語処理系記述の言語
も言語じゃないってわけだな
問題解決手段の一つではあるかもしれないが
通信系ソフトウェアの存在はどう説明？

既存の資産を維持しより効率的に活用する研究が
新しいプログラミング言語が次々と生成されてくる原
動力じゃないかと

986 ：デフォルトの名無しさん：2019/02/03(日) 05:08:39.33 ID:l3Qt7IvN.net

>>982
>日本語だったら英語を知らなくてもノーベル賞が取れるだけの教材(ライブラリ)が揃ってる。

ダウト。ノーベル賞を受賞した研究者はみんな英語で論文書いている。
あと、今の日本語での教育教材の蓄積があるのは、大雑把に言って、
ここ10年でノーベル賞受賞した面々の世代の研究者や技術者が書いた。
もちろん彼らは英語の文献を読み、勉強し、日本語の文献を書いた。
だから、英語の文献なんて要らないみたいな話はアホ。
ソファでポテチ食いながら「ジャガイモなんて買えばいいんだから、育ててる奴はアホ」と言ってるようなもの。

987 ：981：2019/02/03(日) 05:15:20.75 ID:l3Qt7IvN.net

プログラミング言語も一緒。
Cは泥臭い実用言語で、その前にはAlgolなど「綺麗な」言語が下敷きとしてあった。
Cは現在でも多くの問題を解決するための道具として活用されているが、
現在では使われていないAlgolなどの「綺麗な」言語なしにCは生まれなかった。

988 ：デフォルトの名無しさん：2019/02/03(日) 05:39:02.55 ID:1lu6X4vo.net

個々の言語の歴史観の講釈はスレ違い

確かに問題解決の道具であることが
中心かもしれないが、扱ってきた問
題の種類によって文法やライブラリ・
その取り扱い方に差異が生じている
が、同じ問題を別言語で「解く」と
優劣の違いがわかって面白いかもし
れない。
が、あんまし長くやってると不毛な
言語比較論、文化比較論になったり
して色々ヤバいからそろそろ一旦
お開きにしたら？
続きはそれぞれの言語別スレッドで
ということで

989 ：デフォルトの名無しさん：2019/02/03(日) 07:04:30.87 ID:LaZtKDWq.net

お題：プログラムの実行時刻が午前なら「おはようございます、ご主人様！」、午後なら「お疲れ様です、ご主人様！」と表示させる

990 ：デフォルトの名無しさん：2019/02/03(日) 07:48:34.73 ID:AEg+fU/i.net

>>989 C
time_t now = time(NULL);
struct tm *p = localtime(&now);
if (p->tm_hour * 60 + p->tm_min < 12 * 60) {
  printf("おはようございます、ご主人様！\n");
} else if (p->tm_hour * 60 + p->tm_min > 12 * 60) {
  printf("お疲れ様です、ご主人様！\n");
}

991 ：デフォルトの名無しさん：2019/02/03(日) 08:56:17.85 ID:l3Qt7IvN.net

>>989
Pharo Smalltalk

Smalltalk ui inform: (Time now meridianAbbreviation = 'AM' ifTrue: [ 'おはようございます、ご主人様！' ] ifFalse: [ 'お疲れ様です、ご主人様！' ])

992 ：デフォルトの名無しさん：2019/02/03(日) 09:19:47.58 ID:72eosYJ+.net

python

from datetime import datetime
if datetime.now().hour < 12:
print('おはようございますご主人様')
else:
print('お疲れ様です、ご主人様')

993 ：デフォルトの名無しさん：2019/02/03(日) 09:23:27.86 ID:1lu6X4vo.net

午前12時=00:00
午後12時=12:00
23:59の後は00:00

午前12時=12:00
午後12時=24:00
24:00の後は00:01

994 ：デフォルトの名無しさん：2019/02/03(日) 09:40:26.58 ID:cfde/ig7.net

>>865 Common Lisp
https://pastebin.com/TLD3d9R1

実行結果
https://i.imgur.com/6Dne4jz.png

995 ：デフォルトの名無しさん：2019/02/03(日) 09:58:12.21 ID:I0qputsI.net

>>969 のHaskell版。
負の数の場合の処理、負の数含め、絶対値が256以上だった場合エラー吐く様に処理を追加。
※Haskellは整数と少数を明確に分ける為、渡す数に小数点が無いとエラーになる。

mysqrt x = mysqrt' x 0
where
mysqrt' x m |x < 0 = - mysqrt (abs x)
mysqrt' x m |x == m * m = m
mysqrt' x m |x < m * m = fsqrt x (m - 1) 0.1 15
mysqrt' x m = mysqrt' x (m + 1)

fsqrt _ a _ 0 = a
fsqrt v _ _ _ | v > 256 = error "\"fsqr\":out of range 0..256"
fsqrt v a f n | v <= a * a = fsqrt v (a - f) (f * 0.1) (n - 1)
fsqrt v a f n = fsqrt v (a + f) f n

使用例

main = print (mysqrt x) >> print (mysqrt x * mysqrt x)

結果

1.41421356237309
2.0

996 ：デフォルトの名無しさん：2019/02/03(日) 10:00:13.11 ID:I0qputsI.net

fsqrt v _ _ _ | v > 256 = error "\"fsqr\":out of range 0..256"
fsqrt v a f n | v <= a * a = fsqrt v (a - f) (f * 0.1) (n - 1)
fsqrt v a f n = fsqrt v (a + f) f n

997 ：デフォルトの名無しさん：2019/02/03(日) 10:13:31.71 ID:xEPkQ4sk.net

この改行長文おじさんはどこからきたの。笑

998 ： ：2019/02/03(日) 10:31:38.09 ID:t4xt++Qj.net

>>982
＞日本語だったら英語を知らなくてもノーベル賞が取れるだけの教材(ライブラリ)が揃ってる。
最近はそうでもないようですよ…ペーパーは英語だし、教科書＝テキストレベルでも英語でしか発刊されない状況といいます
haskell をやろうとして圏論の教科書を探しましたが、欧米の本の和訳ばかりで日本人が書いた圏論の教科書はありませんでした

999 ：デフォルトの名無しさん：2019/02/03(日) 10:35:41.62 ID:/jO+7TC8.net

誰か次スレ頼む

1000 ：デフォルトの名無しさん：2019/02/03(日) 11:07:15.54 ID:72eosYJ+.net

お題1: 現在地の緯度、経度を出せ
緯度:、、、、
経度:、、、、
お題2: 東京都新宿区西新宿2丁目8-1 の緯度、経度を出せ
緯度:、、、
経度:、、、
お題3: お題2で求めた緯度経度から住所を出せ
郵便番号:、、、
住所:東京都、、、、

1001 ：デフォルトの名無しさん：2019/02/03(日) 11:22:46.76 ID:72eosYJ+.net

立てたよ
プログラミングのお題スレ Part13
https://mevius.2ch.net/test/read.cgi/tech/1549160513/

1002 ：デフォルトの名無しさん：2019/02/03(日) 11:23:36.56 ID:72eosYJ+.net

>>1000 は、次スレに移動させるね。

1003 ：デフォルトの名無しさん：2019/02/03(日) 17:37:12.27 ID:csrqlAvs.net

うめ

1004 ：デフォルトの名無しさん：2019/02/03(日) 17:37:50.59 ID:oUppVF8S.net

>>969
今までの苦労は一体。。。

数学的な平方根の近似値は√x = x ^ (1/2)だった。。。

Haskell だとこんだけ。

mysqrt x = x ** 0.5

1005 ：デフォルトの名無しさん：2019/02/03(日) 17:38:30.96 ID:csrqlAvs.net

次スレ

プログラミングのお題スレ Part13
https://mevius.2ch.net/test/read.cgi/tech/1549160513/

1006 ：2ch.net投稿限界：Over 1000 Thread

2ch.netからのレス数が1000に到達しました。