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

**デフォルトの名無しさん** · 2020/07/14(火) 13:53:46.47

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

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

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

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

**デフォルトの名無しさん** · 2020/09/12(土) 21:24:36.97

お題：自然数nが現れる九九の表の最小サイズを求めよ

octave
https://ideone.com/JyIBOD

**デフォルトの名無しさん** · 2020/09/13(日) 00:20:13.60

>>509
Java
https://paiza.io/projects/brUcg8fsPPrD3ERaUkVOUA

**デフォルトの名無しさん** · 2020/09/13(日) 00:35:46.34

>>509
Kotlin
https://paiza.io/projects/SEi0xU2p5t0WDBvQdAUh3A

良いアルゴリズムが思いつかなかったのでほとんど力技。

**蟻人間** ◆T6xkBnTXz7B0 · 2020/09/13(日) 22:12:25.49

お題: 「ジャンケンすたじあむオンライン」というソーシャルゲームのウェブサイト、もしくはソフトウェアパッケージを制作・運営せよ。

ジャンケンをしたい人が集まって、ひたすらジャンケンをして、勝ち数を競うというソーシャルゲーム。

ジャンケン試合は2人組になり、お互いに出す手を事前に申告し、両者が申告したところでシステムが自動で勝敗を判定する。

**デフォルトの名無しさん** · 2020/09/13(日) 22:17:50.99

>>512
消えろ

**デフォルトの名無しさん** · 2020/09/13(日) 22:22:25.86

動的計画法ってちゃんと勉強しないとなかなか思いつかないよな

**デフォルトの名無しさん** · 2020/09/14(月) 12:06:08.48

>>509
Haskell

f x = head [ d | d <- [(ceiling $ sqrt $ fromInteger x)..], mod x d == 0]
main = mapM_ print [(x,f x) | x<-[100..130]]

**蟻人間** ◆T6xkBnTXz7B0 · 2020/09/14(月) 14:12:59.44

お題: 沖縄の名物「シークワーサー」のことが書かれた記事のUTF-8日本語テキストファイル「input.txt」がある。
しかし、記事の執筆に多数の編集者が関わったため、シークワーサーの表記がぶれていることが分かった(次のリンクを参照)。

https://ja.m.wikipedia.org/wiki/%E3%82%B7%E3%83%BC%E3%82%AF%E3%83%AE%E3%83%BC%E3%82%B5%E3%83%BC

表記のぶれを「シークワーサー」に表記を統一したテキストファイル「output.txt」を出力せよ。

**デフォルトの名無しさん** · 2020/09/14(月) 17:05:19.85

エンジニアが書いてるならシークワーサだな
間違いない

**蟻人間** ◆T6xkBnTXz7B0 · 2020/09/14(月) 17:29:10.23

>>516 input.txtの中身:

「シークヮーサーは、別名シイークワシャーと呼ばれ、シークヮーサーの香りがするシークヮーシャーのような柑橘系の果物である。シィークアーサーはアーサー王とは関係がないと思われる。」

**デフォルトの名無しさん** · 2020/09/14(月) 18:00:53.92

"/シ(?:イ?ー|ィー?)ク[アワァヮ]ー?(?:サ|シャ)ー?/シークヮーサー/g"

**蟻人間** ◆T6xkBnTXz7B0 · 2020/09/14(月) 20:32:57.79

お題: お使いのプログラム言語で、COBOLに負けない最強の通貨型を設計せよ。

任意の桁数の10進整数を扱えること。
任意の有効桁数の10進小数を扱えること(10進浮動小数点数)。
加減乗除、剰余、任意桁での切り捨て・切り上げ・四捨五入が可能。
10進数表記で入出力できること。
比較的高速に演算できること。

**蟻人間** ◆T6xkBnTXz7B0 · 2020/09/14(月) 20:55:28.62

1÷3をどう扱うかという問題があるようだ。

**デフォルトの名無しさん** · 2020/09/14(月) 21:04:18.95

割り算するときに桁数していするだけっしょ

**デフォルトの名無しさん** · 2020/09/14(月) 21:07:19.27

蟻人間さんにお題：銀行丸めを整数型のみを使用して実装してください

**デフォルトの名無しさん** · 2020/09/14(月) 21:08:24.84

>>517
草

**デフォルトの名無しさん** · 2020/09/14(月) 21:24:52.09

昔から思っているんだけど、分数で持っていて最後に一回だけ割り算するんじゃなんでいけないのかな?

**デフォルトの名無しさん** · 2020/09/14(月) 21:26:17.95

昔から思っているんだけど、分数で持っていて最後に一回だけ割り算するんじゃなんでいけないのかな?

**デフォルトの名無しさん** · 2020/09/14(月) 21:49:38.28

分子や分母に分数が入ってきた場合
精度の面で面倒なことになるぞ

**蟻人間** ◆T6xkBnTXz7B0 · 2020/09/14(月) 23:12:41.48

>>523

https://ideone.com/sRja3A
今日はここまで。

**デフォルトの名無しさん** · 2020/09/14(月) 23:41:27.65

>>528
一生ここまでにしろ

**デフォルトの名無しさん** · 2020/09/15(火) 00:21:13.43

>>516

sed -r 's/シ([イィ]ー?|ー)ク[アァワヮ]ー?(サ|シャ)ー/シークワーサー/g'

-r は拡張正規表現を使うオプション。
これで >>518 の文を変換するとこうなる。

「シークワーサーは、別名シークワーサーと呼ばれ、シークワーサーの香りがするシークワーサーのような柑橘系の果物である。シークワーサーはアーサー王とは関係がないと思われる。」

**蟻人間** ◆T6xkBnTXz7B0 · 2020/09/15(火) 02:31:45.89

現実問題では、long double型で十分な精度が出るから、独自の浮動小数点数は必要なさそう。

残りは四捨五入とか銀行丸めなどの端数処理。

**デフォルトの名無しさん** · 2020/09/15(火) 09:10:08.88

工ｴｴｪｪ(´д｀)ｪｪｴｴ工

**デフォルトの名無しさん** · 2020/09/15(火) 14:07:27.97

bc コマンド使えば良い。
他の言語から使いたい場合はライブラリをリンクするか、またはこっそり裏で fork(), exec() してパイプで繋いで計算させるw

**蟻人間** ◆T6xkBnTXz7B0 · 2020/09/15(火) 21:40:23.58

>>528
https://github.com/katahiromz/Currency
今日はここまで。足し算、引き算、掛け算を実装。
銀行丸めはもうちょっと待ってね。

**デフォルトの名無しさん** · 2020/09/15(火) 21:59:54.94

>>534
誰も待ってないから一生滞ってろ

**蟻人間** ◆T6xkBnTXz7B0 · 2020/09/15(火) 22:50:58.78

>>535
スレチ

**蟻人間** ◆T6xkBnTXz7B0 · 2020/09/15(火) 22:54:46.37

>>535
とりあえずまあソースコードを読んで頂いてクレヨン。

**デフォルトの名無しさん** · 2020/09/15(火) 22:56:56.50

ここはお前の日記帳じゃねぇっての
スレチはお前

**デフォルトの名無しさん** · 2020/09/16(水) 10:06:16.52

ぶぶ漬けどうぞと言われて、美味しくいただいてさらに食レポまで始めてるような状態かな

**デフォルトの名無しさん** · 2020/09/16(水) 21:28:53.90

嫌味なことするなよ

**デフォルトの名無しさん** · 2020/09/17(木) 00:07:22.39

京都のおっかさんも口あんぐりやで

**デフォルトの名無しさん** · 2020/09/17(木) 01:09:05.65

>>520 Python decimal でできるだろ。

https://docs.python.org/ja/3/library/decimal.html

**デフォルトの名無しさん** · 2020/09/17(木) 07:37:06.63

お題: (複数行のバックグラウンド、座標テキスト、座標）から合成テキストを返す関数を作れ
座標テキストとバックグラウンドは同じサイズ(とりあえず横4縦3とする)

background
┏┓┏┓
┃┗┛┃
┗━━┛

座標テキスト
ab23
9014
8765

座標が
0なら
┏┓┏┓
┃*┛┃
┗━━┛
6なら
┏┓┏┓
┃┗┛┃
┗━*┛
11なら
┏*┏┓
┃┗┛┃
┗━━┛
あまり綺麗な実装が出来なかったから問題にした https://repl.it/@vip0/analogclock#index.js

**デフォルトの名無しさん** · 2020/09/17(木) 08:03:03.74

>>543 Ruby
def analogClockStr( h, bg, positions )
(clockStr = bg.dup)[ positions.index( h.to_s(16) ) ] = '*'
clockStr
end

background = '
┏┓┏┓
┃┗┛┃
┗━━┛
'.strip.freeze

positions = '
ab23
9014
8765
'.strip.freeze

puts analogClockStr( 0, background, positions )
puts analogClockStr( 6, background, positions )
puts analogClockStr( 11, background, positions )

**デフォルトの名無しさん** · 2020/09/17(木) 08:08:23.20

げっ確かに行ごとにreplace必要ないじゃん
何やってんだ俺
ありがとう

**デフォルトの名無しさん** · 2020/09/17(木) 13:17:16.17

>>543
問題の意味がわからない。

**デフォルトの名無しさん** · 2020/09/17(木) 13:30:29.78

>>543
くだらない質問スレか初心者質問スレ行け

**デフォルトの名無しさん** · 2020/09/17(木) 13:34:08.96

ほんとにどの問題よりもクソみたいな問題だと思っています
本当にすいませんでした

**デフォルトの名無しさん** · 2020/09/17(木) 13:42:30.73

ただ私は純粋にプログラミングが好きで
全く質問したかったわけじゃないのはわかってほしい
二次配列じゃないと処理できないものだと勘違いしていたのが甘いしシンプルにしすぎて問題が破綻してしまった

**デフォルトの名無しさん** · 2020/09/17(木) 13:48:33.25

純粋にここにいる人たちが解法として書くコードは好きだし
たまに驚くべき角度から解を出す人もいるしマイナーなアルゴリズムも知れて尊敬してる
今回もスマートなコードが見れるんじゃないかと純粋に期待して問題にしてみたんだ
スレも今流れ遅かったし

**デフォルトの名無しさん** · 2020/09/17(木) 13:50:39.09

しかしお前らは牙を向いた
純粋に問題作成初心者の心を無碍にして
鋭い刃のような言葉を投げつけてきた
お前らは今日から敵とみなす

あばよ😎✋絶望しな

◆QZaw55cn4c · 2020/09/17(木) 19:40:19.09

>>551
奏ちゃん「自意識過剰なんじゃないですか？」

**デフォルトの名無しさん** · 2020/09/17(木) 22:33:12.99

お題:文字列の末尾の数字をインクリメントしてください

入力
IB0AAYR8ZZcUXLxKmL1ow8RxZAAUCS1j6pYOJo9n52mwITWoimM3UArCpKAGzSRZrA1vUpAerENynuJXTYuJb9HlO9NZvHdpFvCMsThVOnxhgx3T5jCfRhanH4bJJOvjoaTMdixKg4TC90zOCwyeVKJ62KAgv47P72sfPsQaH8jaG8yWnqbwtyv0OeKZa7qISm6g2MHrOlNb8RVzt36jau1hYCqKuuUBGLGuFToYptzqjkfdAoxAqqmeQO7PVcUS
出力
IB0AAYR8ZZcUXLxKmL1ow8RxZAAUCS1j6pYOJo9n52mwITWoimM3UArCpKAGzSRZrA1vUpAerENynuJXTYuJb9HlO9NZvHdpFvCMsThVOnxhgx3T5jCfRhanH4bJJOvjoaTMdixKg4TC90zOCwyeVKJ62KAgv47P72sfPsQaH8jaG8yWnqbwtyv0OeKZa7qISm6g2MHrOlNb8RVzt36jau1hYCqKuuUBGLGuFToYptzqjkfdAoxAqqmeQO8PVcUS

**デフォルトの名無しさん** · 2020/09/17(木) 22:56:25.54

>>553 vim

?\d<CR><C-a>

**デフォルトの名無しさん** · 2020/09/17(木) 23:01:20.65

>>553 Ruby

$><<gets.sub(/\d+(?=\D+$)/, &:succ)

# => IB0AAYR8ZZcUXLxKmL1ow8RxZAAUCS1j6pYOJo9n52mwITWoim
M3UArCpKAGzSRZrA1vUpAerENynuJXTYuJb9HlO9NZvHdpFvCMsThVOn
xhgx3T5jCfRhanH4bJJOvjoaTMdixKg4TC90zOCwyeVKJ62KAgv47P72sfP
sQaH8jaG8yWnqbwtyv0OeKZa7qISm6g2MHrOlNb8RVzt36jau1hYCqKuu
UBGLGuFToYptzqjkfdAoxAqqmeQO8PVcUS

**デフォルトの名無しさん** · 2020/09/18(金) 01:44:05.02

>>553
Perl

コマンドラインで以下のように入力後に標準入力から文字列を読ませると標準出力に出力される。

perl -pe 's/(\d+)(\D+)$/($1+1).$2/ge'

あるいはファイルに内容を入れておいてそのファイルを指定する。

**デフォルトの名無しさん** · 2020/09/18(金) 03:22:29.90

js
window.prompt().replace(/\d(?=\D+$)/,i=>i*1+1)

**デフォルトの名無しさん** · 2020/09/18(金) 06:23:31.29

>>556
行末が数字のときに対応できない
perl -pe 's/(\d+)(\D*)$/($1+1).$2/e'
のほうがよくないかな

**デフォルトの名無しさん** · 2020/09/18(金) 06:53:31.48

>>511
その場合の良いアルゴリズムって
「素因数分解を早く解くアルゴリズム」
よね。
それがもし思いついたらフィールズ賞ものではw

**デフォルトの名無しさん** · 2020/09/18(金) 21:10:31.47

>>553
Java
https://paiza.io/projects/X0KHD9cQEH8LTka6nmDd_w

**デフォルトの名無しさん** · 2020/09/18(金) 21:36:05.11

>>544
Java
https://paiza.io/projects/ka8qfAJFIag1eovg263vzg

**デフォルトの名無しさん** · 2020/09/18(金) 21:54:28.27

>>553
haskell

theStr = "B0AAYR8ZZcUXLxKmL1ow8RxZAAUCS1j6pYOJo9n52mwITWoimM3UArCpKAGzSRZrA1vUpAerENynuJXTYuJb9HlO9NZvHdpFvCMsThVOnxhgx3T5jCfRhanH4bJJOvjoaTMdixKg4TC90zOCwyeVKJ62KAgv47P72sfPsQaH8jaG8yWnqbwtyv0OeKZa7qISm6g2MHrOlNb8RVzt36jau1hYCqKuuUBGLGuFToYptzqjkfdAoxAqqmeQO7PVcUS"

f x = let
(a,b) = span (\x-> (x<'0') || (x>'9')) $ reverse x
c = show $ (+1) $ read $ return $ head b
in reverse $ a++c++(tail b)

main = do
print $ f theStr

**デフォルトの名無しさん** · 2020/09/18(金) 23:21:52.09

>>558
そうだった。 + じゃなくて * だったな。

**253** · 2020/09/18(金) 23:34:45.95

>>559
素因数分解まで行かない。
素でなくてもいいので因数のうちイチバン大きいもの。
なんかいい解法見つけられないか、考えているけどいまのところ見出せていない

**253** · 2020/09/18(金) 23:36:27.35

いや、違うな…
因数のうちイチバン大きいものでは、ﾀﾞﾒだわ

**デフォルトの名無しさん** · 2020/09/19(土) 00:05:40.30

>>553
C

https://paiza.io/projects/IEDhYc83EDXZuCbsxf_QUg

正規表現を使わずに行末から一文字づつ行頭に向かって検索してやっている。

**デフォルトの名無しさん** · 2020/09/19(土) 00:59:21.89

√n以上の最小の約数

**デフォルトの名無しさん** · 2020/09/19(土) 12:14:05.54

初出題
数学板の問題より

５つのサイコロの1～6の面がそれぞれ赤白黄青緑にそれぞれ

["byrbwg", "yrgwbb", "gbrwwy", "gyrbww", "gbrybw"]

と塗り分けられている
この状態では1-6を天地の軸として2～5の側面にはそれぞれ

["yrbyb","rgrrr","bwwby","wbwwb"]

となっている
それぞれのサイコロを適当に回転させて全ての側面にrwybgがちょうど一回ずつとなるようにしたい
そのような回転の組み合わせは何通りか
本質的に同じものを重複して数えるのを避けるために最初のサイコロの回転は
・動かさない
・1→2,2→3,3→1,4→6,5→4,6→5
・1→3,2→1,3→2,4→5,5→6,6→4
の3つのうちどれかのみを許すとする
(出力)
["yrbgbw","gbybrw","bgwryw","bygwwr","bwrygb"]
["yrbgbw","gbybrw","wywrgb","rwgwyb","bgrywb"]
["rbywgb","gyrbbw","wwgyrb","ygbrww","brwgyb"]
["rbywgb","wybrbg","wwgyrb","wgrbwy","brwgyb"]

**デフォルトの名無しさん** · 2020/09/19(土) 15:12:41.86

https://rio2016.5ch.net/test/read.cgi/math/1598637093/133-
わけわからん問題文にするなよ・・・

**デフォルトの名無しさん** · 2020/09/19(土) 16:07:21.18

全然違って草

**デフォルトの名無しさん** · 2020/09/19(土) 16:29:35.90

>>568
君が何を言わんとしているのかが全くわからない。

**253** · 2020/09/19(土) 17:15:41.66

>>509 Perl5、>>567にﾋﾝﾄを貰った通り√を使ってnaiveに書くと…

use POSIX 'ceil';
for $n (81, 87, 91) {
　$r = ceil sqrt $n;
　for ($r..$n) {
　　$i = $_;
　　last until $n % $_;
　}
　print "$n => $i\n"
}

実行結果
~ $ perl 18_509_99_naive.pl
81 => 9
87 => 29
91 => 13

計算量の少ないもう少しｶｯﾁｮｲｲ方法を見出せればなぁ…

**デフォルトの名無しさん** · 2020/09/19(土) 21:37:57.70

>>568です
やはりちょっと伝わらないですね
>>568
は取り下げます

**デフォルトの名無しさん** · 2020/09/19(土) 21:39:46.15

>>572
計算量減らすなら√n以下の最大の約数d求めてn/dを出力すれば計算量は減るな

**デフォルトの名無しさん** · 2020/09/19(土) 21:40:46.29

減るというかそもそも計算量が同じというか

**デフォルトの名無しさん** · 2020/09/19(土) 21:46:21.17

イヤnが素数の場合に√nから上むきに探索すると計算量はnになるけど下向きなら√nになる
√n以上の約数と√n以下の約数は同数だけど整数そのものは下側には√nしかなく、上にはn-√nあるので下向きに探していった方が速い

**デフォルトの名無しさん** · 2020/09/20(日) 00:25:54.87

ポラード・ロー法使えばもっと計算量は減る
素数判定と組み合わせればモンテカルロ法ではなくラスベガス法になるから、正当性も担保される

**デフォルトの名無しさん** · 2020/09/20(日) 01:39:54.18

素因数分解利用するなら素因数分解そのものが手早くできてもダメでしょ？
それを何個か使って最も√nに近いもの探すのはかなり難しいんじゃなかったっけ？
つまり素因数分解n=Πpi^eiが与えられたとして、つぎは
0≦xi≦eiを動かすときΣxi log(pi) が1/2 log(n)に最も近くなるものを決定しなければならない
コレなんか名前ついてる問題で指数オーダーのアルゴリズムしか見つかってないんじゃなかったっけ？
素因子の数はlog(n)のオーダーで増えていくから、結局exp(c log(n)) のオーダーになって、cがどれくらいに収められるか、そもそも指数オーダー必要なのかも未解決なんじゃなかったっけ？

**デフォルトの名無しさん** · 2020/09/20(日) 06:22:49.81

>>576
素数判定はそもそも計算量少ない

**デフォルトの名無しさん** · 2020/09/20(日) 10:19:03.22

>>579
√n以上の最小の約数をdとして上むき探索に必要な時間はすうがく/d-√n\、下向き探索のそれは\√n-n/d/ (/～\と\～/はfloorとceiling)
差は/d-√n\-\√n-n/d/ =\d+n/d-2√n/はam≧gmと\～/の広義単調性から0以上で上むき探索は素数であるか否かに限らず常に計算量は同じかそれ以上
素数であるか予備検査しても結局上向きに探索したら計算量は同じ以上かかる

**デフォルトの名無しさん** · 2020/09/20(日) 10:50:48.99

あ、間違えた
上向き探索の探索量はd-/√n\+1=/d-√n+1\で/~\はceiling
下向き探索の探索量は\√n/-n/d+1=\√n-n/d+1/で\~/はfloor
まぁ常に上向きの方が計算量は増える
まぁもちろんnをまともに素因数分解して>>578みたいな方法で√nオーダーより真に早いのがあるなら上向きも下向きもないけど、もうそこまで行ったら研究者レベルの話でしかない気がする

**デフォルトの名無しさん** · 2020/09/20(日) 11:23:17.24

>>550-551
短いこの間でダークサイドに堕ちてて草

**デフォルトの名無しさん** · 2020/09/20(日) 11:58:05.82

>>582
お詫び→弁解→言い訳→逆ギレ
冷静に書いてたつもりが書いてくうちに興奮して見事なコンボを決めたようだ

**デフォルトの名無しさん** · 2020/09/20(日) 12:47:09.77

感情豊かでかわいいｗ

**デフォルトの名無しさん** · 2020/09/20(日) 12:59:00.77

気分を変えてまた数学板より

自然数nに対して格子点の集合{(a,b) | a,bは1～nの整数}の中の相異なる4点の組みで同一円周上に並ぶものの個数を数え上げよ
n:1～8では
[0,1,14,194,826,2491,6364,14564]
のハズ

**デフォルトの名無しさん** · 2020/09/20(日) 13:05:52.02

>>585
ちなみにn=3の場合の14個は
1×1の正方形:4個
2×2の正方形:1個
√2×√2の正方形:1個
2×1の長方形:4個
4辺が1,1,√2,2√2の等脚台形:4個
の14個

**デフォルトの名無しさん** · 2020/09/20(日) 18:36:43.29

>>585
https://ideone.com/L3IoWm
{0,1,14,184,762,2257,5704,13040}と出たんだが
どっちが合ってる？

**デフォルトの名無しさん** · 2020/09/20(日) 18:44:44.75

一直線上にある４点の組を余分に数えたところ >>585 の解と一致した
https://ideone.com/GUZoZL

**デフォルトの名無しさん** · 2020/09/20(日) 18:56:48.73

あ、ホントだ失礼しました

**デフォルトの名無しさん** · 2020/09/20(日) 19:10:27.22

[0,1,14,184,762,2257,5704,13040]
が正解ですね

https://ideone.com/YULQQ4

**デフォルトの名無しさん** · 2020/09/20(日) 22:46:33.41

>>585
問題がわからない。

**デフォルトの名無しさん** · 2020/09/21(月) 00:11:09.46

>>591
n=3だと

●●◯ ◯●● ◯◯◯ ◯◯◯
●●◯ ◯●● ●●◯ ◯●●
◯◯◯ ◯◯◯ ●●◯ ◯●●

●◯● ◯◯◯ ●●◯ ◯●●
●◯● ●◯● ◯◯◯ ◯◯◯
◯◯◯ ●◯● ●●◯ ◯●●

●●◯ ◯●● ◯◯● ●◯◯
◯◯● ●◯◯ ◯◯● ●◯◯
◯◯● ●◯◯ ●●◯ ◯●●

●◯● ◯●◯
◯◯◯ ●◯●
●◯● ◯●◯

の14通り

**デフォルトの名無しさん** · 2020/09/21(月) 11:36:08.07

>>585のお題は、
平面上に４点を選んだとき、その４点をすべて含む円周が存在する場合としない場合がある
xy平面上に、x,yの各座標が1～nの整数であるような、互いに異なる点を４つ選んだとき、４点すべてを含む円周が存在するものがいくつあるか？
n=1～8についてそれぞれ数え上げよ
(註:n=1のときは異なる４点を選べないので、解は０でよい)

ってことでいいかな？

**デフォルトの名無しさん** · 2020/09/21(月) 13:45:14.08

>>592
n=4 のときの184通り
http://imgur.com/GNuPa4z.png

**デフォルトの名無しさん** · 2020/09/21(月) 14:54:29.54

>>594
正解だと思う
おそらくn=9までは

[0,1,14,184,762,2257,5704,13040,25996]

今作ってるのはC[n^2,4]を全数検査してるのでO(n^8)で計算量増えるので二桁以上はしんどいorz

**デフォルトの名無しさん** · 2020/09/22(火) 00:03:46.43

誰かフォルダにパスワード駆ける方法教えてくれ

**253** · 2020/09/22(火) 02:15:18.79

対象性を考慮する以外の計算量の削減手段はないのかねこの手の問題は
解決すべき課題は計算量の削減ばかりではないだろうけれどさ

**デフォルトの名無しさん** · 2020/09/22(火) 09:28:15.64

まぁ何に重きを置くかですな
数学板でこの手のプログラムが必要になるのは誰も答え持ってなくて、一応答えは出てるけど確認したいときとか
その時は速度より“確実に正しい”事の方が重要になる
この場合も対称性やら、明らかに無駄な可能性を排除すれば速度は上がるけど“確実に正しい”のかは怪しくなってしまう
実務でプログラム使う人もその辺のtpoは意識してるのでは？、
コード汚くても高速な奴も募集中

**デフォルトの名無しさん** · 2020/09/22(火) 11:56:55.93

>>594に挙げられている184通りのうち、その3/4にあたる138通りが、直径が√10のものである
そのうち、円の中心が図の中央にあるものは、候補となる点が8個あるので、8C4 = 70 通りある。
図の中央から(±1,0)または(0,±1)ずれたものは、候補となる点が6個なので4×(6C4)=60通り
図の中央から(±2,0)または(0,±2)ずれたものが、候補となる点が4個なので4×(4C4)=4通り
図の中央から(±1,±1)ずれたものが、候補となる点が4個なので4×(4C4)=4通り
合わせて 70+60+4+4=138 通りと数え上げることができる

図の中央を基準にすることができるものばかりとは限らないところには注意が必要だが
総当たりよりは効率化が見込めると思われる。

**253** · 2020/09/28(月) 22:51:28.57

>>509 Python3, >>576を参考に計算量を√nに減らした解法

import math
for n in [81, 87, 91, 13]:
　　s = math.sqrt(n)
　　f = n
　　for i in reversed(range(2, 1 + math.floor(s))):
　　　　q, m = divmod(n, i)
　　　　if m == 0: f = q; break
　　print(n, '=>', f)

実行結果
~ $ python 18_509_99_rootn.py
81 => 9
87 => 29
91 => 13
13 => 13

もっとスマートな解法を考えていると双曲線を意識した解法を意識してしまうが、
簡単には解けない数学の問題に突き当たると思う

**253** · 2020/09/28(月) 22:53:47.02

>>600
× 意識した解法を意識してしまうが、
○ 意識した解法を思い浮かべてしまうが、

**デフォルトの名無しさん** · 2020/09/29(火) 18:23:40.44

お題: バブルソートを実装せよ

**253** · 2020/09/29(火) 23:24:18.49

>>602
プログラミングのお題スレ Part13
http://mevius.5ch.net/test/read.cgi/tech/1549160513/231

**デフォルトの名無しさん** · 2020/09/30(水) 20:15:38.19

古参はここで「番兵おけやボケェ！」と言う

**デフォルトの名無しさん** · 2020/10/01(木) 01:25:55.75

お題:
アッカーマン関数の引数が与えられるので、計算過程を1ステップずつ出力してください

入力:
2 1

出力:
A(2, 1)
A(1, A(2, 0))
A(1, A(1, 1))
A(1, A(0, A(1, 0)))
A(1, A(0, A(0, 1)))
A(1, A(0, 2))
A(1, 3)
A(0, A(1, 2))
A(0, A(0, A(1, 1)))
A(0, A(0, A(0, A(1, 0))))
A(0, A(0, A(0, A(0, 1))))
A(0, A(0, A(0, 2)))
A(0, A(0, 3))
A(0, 4)
5

**デフォルトの名無しさん** · 2020/10/01(木) 11:20:33.49

>>605
Haskell

astr m n = "A(" ++ m ++ "," ++ n ++ ")"
ack' 0 n = (n+1, [astr (show 0) (show n), (show $ n+1)])
ack' m 0 = let
(val, ss) = ack' (m-1) 1
in (val, (astr (show m) (show 0)) : ss)
ack' m n = let
(val1, ss1) = ack' m (n-1)
(val2, ss2) = ack' (m-1) val1
ss = [astr (show $ m-1) s | s <-ss1] ++ (tail ss2)
in (val2, (astr (show m) (show n)):ss)
ack m n = map (++"\n") $ snd $ ack' m n

main = do
[x,y]<-(return.(map read).words)=<<getLine
mapM_ putStr $ ack x y

**デフォルトの名無しさん** · 2020/10/01(木) 12:09:11.51

Haskellでもこんな長くなるの？

**デフォルトの名無しさん** · 2020/10/01(木) 12:15:24.40

>>607
いや、上手な人ならもっと上手くやるはず
アホほどライブラリがあってそれ使えば楽々のハズだけど修行中の身ではこんなもんorz