プログラミングのお題スレ 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/

**デフォルトの名無しさん** · 2019/01/31(木) 17:40:00.64

>>860 Lua
print("░")
横から見た

**デフォルトの名無しさん** · 2019/01/31(木) 17:57:03.10

>>936 python の場合、これじゃいかんのか？まだ全くpythonを知らん人間だが。

scipy.special.comb(n, k, exact = False)

python はライブラリを使ってなんぼでしょ。生の言語で比較するのは時代遅れ。なんで膨大な処理が必要なAI でpython が主流になったか。

**デフォルトの名無しさん** · 2019/01/31(木) 18:21:11.67

ライブラリを紹介するスレじゃないんだが。
mathjs
math.combinations(7, 5)

こういうの延々と続けるの？
バカじゃないのｗｗｗ

**デフォルトの名無しさん** · 2019/01/31(木) 18:41:17.06

>>943 別に構わんだろ。そもそも言語なんてやりたいことを解決するのに便利かどうかだけの話なんだから。

そういう意味では、普通のことをやるにはどの言語でも大差はない。

FORTRAN なんて大昔の言語だがいまだに科学技術計算で使われ続けてきているのは、言語仕様ではなく高速なライブラリが整ってるからに他ならない。

なんでAI や科学技術計算にスクリプト言語のpython がもてはやされてるのかもう一度考えてみる必要があるのでは？

**デフォルトの名無しさん** · 2019/01/31(木) 18:50:20.38

いくら言語が優れていても、ある特定の環境だけでしか実用性がない言語と言うのは、別環境用のライブラリが整っていないからに他ならない。

例えばSwift これは、Mac環境下ではObjective-C の全てが使えるが、
言語的にはWindows などでコンパイルできても、ライブラリがないから実用として使うにはまだ程遠い。
API が整っていることが重要。

python がもてはやされてるのは、ライブラリが整ってるからだろ。言語の良さがどうかなんてあまり関係ない。
ま、個人的な好き嫌いが出てくるのは仕方ないが、実用性があるかどうかはまた別の問題。

**デフォルトの名無しさん** · 2019/01/31(木) 18:58:10.77

そもそも、言語なんてアセンブラの時代からマクロで自分好みの文をかけるようになってたんだから、今更何を議論してるのかという気もする。

標準化された文法というのは評価はするが、それはどっちかと言うと頭でっかちな学者が考えること。
現場はいかにバグが少なく早く問題を解決できるかにかかってる。つまり総合環境だろ。

**デフォルトの名無しさん** · 2019/01/31(木) 18:59:37.75

溜まってたものを一気に語ったな

**デフォルトの名無しさん** · 2019/01/31(木) 19:46:27.30

うむ。これからの時代はファミリーBASICだな。

**デフォルトの名無しさん** · 2019/01/31(木) 19:59:18.32

>>948 最初の頃のBASICは、10数個位しか命令は無かった。
ま、電卓がわりみたいなものでは有るが、基本的なプログラミング言語としては成り立ってた。

**デフォルトの名無しさん** · 2019/01/31(木) 20:11:31.45

>>942
たまたま、ライブラリで解決出来る問題だからってマウント取られてもね。。。
それに、C/C++みたいに多倍長整数サポートしてない言語と、サポートしてる言語でのアルゴリズムの違いや、
式変形して引き算を足し算に変えられる所は変えた方が速度出るとか、色々勉強にはなってるよ。
>>936の例じゃ(n - (r - 1))を(n - r + 1)にした方が速い。
(Haskellでは速いだけでなく、2の補数表現を(元の数値と別に)生成してるらしく、メモリ効率も上がる)

**デフォルトの名無しさん** · 2019/01/31(木) 21:19:24.42

>(n - (r - 1))を(n - r + 1)にした方が速い。

>>950 あのさ、そんなのはコンパイラの最適化次第だろ。勿論ど素人のプログラマじゃ無ければそれなりの工夫はするはずだが、そんな事は些細な事。くだらんことを言うな。むしろそんなコンパイラがクソ。言語なんてのは言語道断。

**デフォルトの名無しさん** · 2019/01/31(木) 22:25:01.31

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

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

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

**デフォルトの名無しさん** · 2019/01/31(木) 22:46:32.84

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

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

**デフォルトの名無しさん** · 2019/02/01(金) 04:58:43.05

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

**デフォルトの名無しさん** · 2019/02/01(金) 10:08:25.26

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;
}

**デフォルトの名無しさん** · 2019/02/01(金) 18:32:58.66

>>954
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

**デフォルトの名無しさん** · 2019/02/01(金) 20:32:42.61

Python

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

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

**デフォルトの名無しさん** · 2019/02/01(金) 21:10:55.66

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

**デフォルトの名無しさん** · 2019/02/01(金) 21:19:45.40

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

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

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

**デフォルトの名無しさん** · 2019/02/01(金) 22:13:46.18

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

**デフォルトの名無しさん** · 2019/02/01(金) 23:10:20.49

>>958
m = ？
n = m * m

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

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

**デフォルトの名無しさん** · 2019/02/01(金) 23:12:44.04

ttps://ideone.com/xr1vcE

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

**デフォルトの名無しさん** · 2019/02/02(土) 00:09:40.70

>>954 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))

**デフォルトの名無しさん** · 2019/02/02(土) 03:47:32.54

いっそ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)

**デフォルトの名無しさん** · 2019/02/02(土) 09:51:18.58

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

**デフォルトの名無しさん** · 2019/02/02(土) 13:18:27.64

平方数かどうかを高速に判定する方法 - 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が計算できるのです。

**デフォルトの名無しさん** · 2019/02/02(土) 13:43:47.68

>>944
えぇ…

**デフォルトの名無しさん** · 2019/02/02(土) 16:31:05.91

>>967 その心は？

**デフォルトの名無しさん** · 2019/02/02(土) 16:42:03.23

>>965
えぇ…

の間違い。

**デフォルトの名無しさん** · 2019/02/02(土) 17:31:46.69

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

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

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

**デフォルトの名無しさん** · 2019/02/02(土) 17:36:46.77

なんしたのきゅうに

**デフォルトの名無しさん** · 2019/02/02(土) 17:57:26.00

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

**デフォルトの名無しさん** · 2019/02/02(土) 19:52:10.51

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

**デフォルトの名無しさん** · 2019/02/02(土) 23:25:24.42

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

**デフォルトの名無しさん** · 2019/02/03(日) 00:45:38.22

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

**デフォルトの名無しさん** · 2019/02/03(日) 00:55:19.58

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

**デフォルトの名無しさん** · 2019/02/03(日) 00:57:22.00

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

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

**デフォルトの名無しさん** · 2019/02/03(日) 01:53:34.29

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

**デフォルトの名無しさん** · 2019/02/03(日) 04:02:35.76

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

**デフォルトの名無しさん** · 2019/02/03(日) 04:46:34.72

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

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

**デフォルトの名無しさん** · 2019/02/03(日) 05:08:39.33

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

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

**981** · 2019/02/03(日) 05:15:20.75

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

**デフォルトの名無しさん** · 2019/02/03(日) 05:39:02.55

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

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

**デフォルトの名無しさん** · 2019/02/03(日) 07:04:30.87

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

**デフォルトの名無しさん** · 2019/02/03(日) 07:48:34.73

>>984 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");
}

**デフォルトの名無しさん** · 2019/02/03(日) 08:56:17.85

>>984
Pharo Smalltalk

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

**デフォルトの名無しさん** · 2019/02/03(日) 09:19:47.58

python

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

**デフォルトの名無しさん** · 2019/02/03(日) 09:23:27.86

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

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

**デフォルトの名無しさん** · 2019/02/03(日) 09:40:26.58

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

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

**デフォルトの名無しさん** · 2019/02/03(日) 09:58:12.21

>>964 の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

**デフォルトの名無しさん** · 2019/02/03(日) 10:00:13.11

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

**デフォルトの名無しさん** · 2019/02/03(日) 10:13:31.71

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

◆QZaw55cn4c · 2019/02/03(日) 10:31:38.09

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

**デフォルトの名無しさん** · 2019/02/03(日) 10:35:41.62

誰か次スレ頼む

**デフォルトの名無しさん** · 2019/02/03(日) 11:07:15.54

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

**デフォルトの名無しさん** · 2019/02/03(日) 11:22:46.76

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

**デフォルトの名無しさん** · 2019/02/03(日) 11:23:36.56

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

**デフォルトの名無しさん** · 2019/02/03(日) 17:37:12.27

うめ

**デフォルトの名無しさん** · 2019/02/03(日) 17:37:50.59

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

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

Haskell だとこんだけ。

mysqrt x = x ** 0.5

**デフォルトの名無しさん** · 2019/02/03(日) 17:38:30.96

次スレ

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

**1001** · Over 1000

このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 128日 7時間 29分 24秒