プログラミングのお題 ..
750:デフォルトの名無しさん
15/09/05 12:41:02.73 l/Jp8teC.net
石が連続してというのは
石が連結してという表現のほうが
わかりやすいか....
751:デフォルトの名無しさん
15/09/05 12:47:13.51 a9CPEVg5.net
>>717
お前が全滅すればいいのにな
完全に論破されたからと言ってまず誰も解答が付かない問題を出すとかガキかよ
752:デフォルトの名無しさん
15/09/05 12:54:53.58 nIE3Kuq7.net
>>665 Emacs Lisp
キーワード引数commaの値が689の場合は>>690と同様に動作するようになりました。
(cl-defun f (s &key comma (truncate 0))
(let* ((aaa (let ((x (string-match "[^0]" s))) (if x (substring s x) "0")))
(bbb (length aaa))
(ccc (* (ceiling (/ (float bbb) 4)) 4))
(lll (if (eq comma 689)
(let ((c 0))
(cl-map 'string (lambda (x) x)
(reverse (cl-mapcan #'(lambda (x) (prog1 (if (and (/= x 32) (/= c 0) (= (% c 3) 0)) (list ?, x) (list x)) (unless (= x 32) (incf c))))
(reverse (string-to-list aaa))))))
(format (format "%%%ds" ccc) aaa)))
(mmm (if (eq comma 689)
(split-string (let ((c 0))
(cl-map 'string (lambda (x) x)
(reverse (cl-mapcan #'(lambda (x) (prog1 (if (and (/= c 0) (= (% c 4) 0)) (list 10 x) (list x)) (unless (= x ?,) (incf c))))
(reverse (string-to-list lll)))))) "\n")
(cl-loop for i from 0 below ccc by 4 collect (substring lll i (+ i 4)))))
(fff (mapcar #'(lambda (x) (if (cl-find #x20 x) (remove #x20 x)
(if (string= (remove ?, x) "0000") "" (if (eq comma 689) x (let* ((i (string-match "[^0]" x)) (y (if i (substring x i) x)))
(if (= (length y) 4) (concat (substring y 0 1) (if (eq comma t) "," "") (substring y 1)) y)))))) mmm))
(ggg (reverse fff))
(hhh (cl-subseq ggg truncate))
(iii '("" "万" "億" "兆" "京"))
(jjj (cl-subseq iii truncate))
(kkk (cl-mapcan #'(lambda (a b) (if (string= b "") nil (list a b))) jjj hhh)))
(apply #'concat (reverse kkk))))
f
(f "1234567890" :comma t) "12億3,456万7,890"
(f "1234567890" :comma 689) "1,2億34,56万7,890"
753:デフォルトの名無しさん
15/09/05 15:47:27.36 u8tdzSFZ.net
>>709
私は15Queenの一つの例を求めているだけです、
コンピュータ内で例えば行列の形で配置を求めているならば、
その一例を表示することはできないでしょうか。
たとえば、すべての配置の数を求めた後で、その最後に求めた
配置を表示するということならば、時間はあまり掛からないと思いますが。
プログラムだけを提示されてもその言語を使える環境にないものに
とっては、このプログラムの正しさを検証するてだてがありませんので。
754:デフォルトの名無しさん
15/09/05 15:52:40.59 1TQgpEDy.net
>>721
お前どんだけしつこいんだよ
じゃお前の書いたプログラムには全くバグがないのか
仕事で書いたプログラムに不具合が見つかっても「仕様です」と言って直さないつもりか
この問題は配置を求める問題ではない
「解の個数」さえ求めればそれでいいんだ
ビットマップを使った解法は外人が世界で一番最初に考案したそうなんでこの人に
「あなたのプログラムは本当に正しいのでしょうか。配置を表示できますか。」と質問を
英語で送ってみなよ
URLﾘﾝｸ(jsomers.com)
この人がそうだ
この人の書いたプログラムと本質的には何ら変わらない
もっと速いアルゴリズムもあるが長くなるので端折っただけ
お前を見てるとお前は人に嫌われる達人だなあと心から感心する
755:デフォルトの名無しさん
15/09/05 16:13:25.93 1TQgpEDy.net
>>721
あ、それとお前頭が悪くて人のプログラムを読み解く力がなさそうだから教えといてやるよ
利き筋のみをチェックするのと配置も同時に求めるのは別の問題だ
どう読んだらこのプログラムの中に配置情報まで入っていると思えるのかそちらの方が不思議なんだが
いくらでも配置も覚えておくプログラムは書けるぞ
むしろこのプログラムは利き筋のみチェックして配置を求めるのを省いた分だけ速くなってるのだと
756: 気付けないのかなあ 真剣に一度精神科で診てもらう事を検討しろよ もう遅いと思うけど
757:デフォルトの名無しさん
15/09/05 17:13:54.12 H2DL4EyO.net
これが噂の炎上学習法か
醜いね
758: ◆QZaw55cn4c
15/09/05 17:25:37.26 bMqKfWg+.net
なりすましに利用されるキャラに成ったとは喜ばしいことだ‥
でも俺じゃないよ
759:デフォルトの名無しさん
15/09/05 18:11:46.68 r36BFiK6.net
>>723
ざっと主張を読むと、>>723は頭いいとおもうけどな
異論あるやついるの？
>>721
このこは、馬鹿というか精神病はいってるいうか、
「云々なだけです」
なんてヤバスギなんだぞ
本人わからんだろうけど
760:デフォルトの名無しさん
15/09/05 18:20:17.60 byXpZJ1D.net
>>721君へ
僕は>>700さんのコードを改竄して配置を表示するようにしてみたよ。
URLﾘﾝｸ(ideone.com)
期待に応えられたかな？？？
761:デフォルトの名無しさん
15/09/05 21:22:45.11 pNQf4xq/.net
>>707
どちらのテストケースも時間が掛かり過ぎるのでもっと小さなデータにしました
データは
URLﾘﾝｸ(pastebin.com)
プログラムは(データを作るプログラムを含んでいます)
URLﾘﾝｸ(ideone.com)
これでこちらの環境ではReleaseモードで700ms前後です
こういうのはやはりC#は苦手なんですかね
すっきり書ける事は書けるんですが
<int>ではなくて<long>になっているのは、intでこれを実行すると大きなデータセットで
オーバーフローが出ちゃうからです
時間が掛かるのは多分順列で天文学的な場合の数になっちゃうからからなあ
762:デフォルトの名無しさん
15/09/05 21:33:50.27 OFlnC1Bs.net
お題：数列を省略して表示してください
数列の範囲 (min, max) と表示数 (disp)、省略の基点 (spot) が以下の範囲内で与えられます。
(0 ＜ min ＜ max), (2 ＜ disp), (min ≦ spot ≦ max)
min 1, max 3, disp 3, spot 1: (1) 2 3
min 1, max 3, disp 3, spot 2: 1 (2) 3
min 1, max 3, disp 3, spot 3: 1 2 (3)
min 1, max 4, disp 3, spot 2: 1 (2) ... 4
min 1, max 4, disp 3, spot 3: 1 ... (3) 4
min 1, max 10, disp 5, spot 1: (1) 2 3 4 ... 10
min 1, max 10, disp 5, spot 2: 1 (2) 3 4 ... 10
min 1, max 10, disp 5, spot 3: 1 2 (3) 4 ... 10
min 1, max 10, disp 5, spot 4: 1 ... 3 (4) 5 ... 10
min 1, max 10, disp 5, spot 5: 1 ... 4 (5) 6 ... 10
min 1, max 10, disp 5, spot 6: 1 ... 5 (6) 7 ... 10
min 1, max 10, disp 5, spot 7: 1 ... 6 (7) 8 ... 10
min 1, max 10, disp 5, spot 8: 1 ... 7 (8) 9 10
min 1, max 10, disp 5, spot 9: 1 ... 7 8 (9) 10
min 1, max 10, disp 5, spot 10: 1 ... 7 8 9 (10)
min 128, max 256, disp 7, spot 192: 128 ... 190 191 (192) 193 194 ... 256
disp が偶数の場合の spot の偏り、
min 1, max 10, disp 4, spot 8: 1 ... 7 (8) ... 10
min 1, max 10, disp 4, spot 9: 1 ... 8 (9) 10
disp が大きい場合の振る舞い、
min 1, max 3, disp 5, spot 3: 1 2 (3)
min 1, max 3, disp 5, spot 3: error. disp out of range
() や ... などの装飾は自由です。
763:デフォルトの名無しさん
15/09/05 21:57:37.63 OFlnC1Bs.net
>>729
(2 ＜ disp) は（0 ＜ disp）でもおｋです
764:デフォルトの名無しさん
15/09/05 22:22:12.08 OFlnC1Bs.net
>>730
やっぱり省略がアレになるので（2 < disp）に訂正します
765:デフォルトの名無しさん
15/09/06 00:53:28.75 3aEa3HTV.net
>>729 Python3
URLﾘﾝｸ(ideone.com)
spotから表示する数を求めていく方法
766:デフォルトの名無しさん
15/09/06 02:03:11.12 labNDWrY.net
NQueenの問題といい、オセロの件といい.QZの自演は凄いな
767:デフォルトの名無しさん
15/09/06 04:26:44.16 3aEa3HTV.net
>>729 OCaml
URLﾘﾝｸ(ideone.com)
>>732と同じアプローチ、ゴリ押しで書き下した
768:デフォルトの名無しさん
15/09/06 06:07:10.46 laHESI+6.net
>>733
QZの自己承認欲求が強すぎるよな
完全に精神的に病気だな
炎上学習法をやるのはQZ一人しかいない
769:デフォルトの名無しさん
15/09/06 08:08:20.90 /Fu+tBiS.net
>>728
ちょっと時間がかか
770:りすぎですね 無理にIEnumerable<T>を返してforeachするより http://d.hatena.ne.jp/JAPLJ/20090123/1232716837 こういう奴の方が速いかもしれないんで試してみてください ちなみにVS2015 C++で>>728のプログラムを書き直したのが http://ideone.com/5bUOrW >>728のデータでこちらで6msしか掛かりませんのでどこかに不自然に 時間がかかりすぎていると思います またこのプログラムはおっしゃる通りどこかでベクトルの大きさが大きいものが 1個でも入るとそこで引っかかります
771:デフォルトの名無しさん
15/09/06 08:17:25.46 3aEa3HTV.net
>>729 Go
URLﾘﾝｸ(ideone.com)
>>732と同じアプローチ、再代入ましまし
772:デフォルトの名無しさん
15/09/06 08:23:56.62 pZj7Wd8c.net
>>729
汚Haskell
URLﾘﾝｸ(ideone.com)
773:デフォルトの名無しさん
15/09/06 12:29:03.84 RC4omDg7.net
>>707 Java
URLﾘﾝｸ(ideone.com)
774:デフォルトの名無しさん
15/09/06 15:06:47.52 mows7ZZ0.net
>>729 Emacs Lisp
(cl-defun f (min max disp spot &key error)
(when (< (1+ (- max min)) disp)
(if error (error "error. disp out of range") (setq disp (1+ (- max min)))))
(let* ((aaa (let (l) (setq l (cl-adjoin min l)) (setq l (cl-adjoin max l))
(let ((i 0))
(while (< (length l) disp)
(let ((y (let ((x (ceiling (/ (float i) 2)))) (+ spot (if (oddp i) (- x) x)))))
(when (and (<= min y) (<= y max))
(setq l (cl-adjoin (let ((x (ceiling (/ (float i) 2)))) (+ spot (if (oddp i) (- x) x))) l))))
(incf i)))
(sort l (lambda (a b) (< a b)))))
(bbb (let ((p (1- min)))
(cl-loop for n in aaa collect (prog1 (list (if (= n (1+ p)) "" "... ") (format (if (= n spot) "(%d)" "%d") n)) (setq p n)))))
(ccc (cl-reduce (lambda (a b) (concat a " " b)) (mapcar (lambda (x) (concat (nth 0 x) (nth 1 x))) bbb))))
ccc))
f
(f 1 3 3 1) "(1) 2 3"
(f 1 3 3 3) "1 2 (3)"
(f 1 4 3 2) "1 (2) ... 4"
(f 1 4 3 3) "1 ... (3) 4"
(f 1 10 5 1) "(1) 2 3 4 ... 10"
(f 1 10 5 3) "1 2 (3) 4 ... 10"
(f 1 10 5 4) "1 ... 3 (4) 5 ... 10"
(f 1 10 5 10) "1 ... 7 8 9 (10)"
(f 128 256 7 192) "128 ... 190 191 (192) 193 194 ... 256"
(f 1 10 4 8) "1 ... 7 (8) ... 10"
(f 1 10 4 9) "1 ... 8 (9) 10"
(f 1 3 5 3) "1 2 (3)"
(f 1 3 5 3 :error t) "error. out of range"
775:デフォルトの名無しさん
15/09/06 15:25:31.21 XK9v3oN2.net
>>729 GNU Smalltalk
URLﾘﾝｸ(ideone.com)
776:デフォルトの名無しさん
15/09/06 15:53:00.71 XK9v3oN2.net
>>699 GNU Smalltalk
URLﾘﾝｸ(www.ic-net.or.jp) を移植。
ideone.com で N=12 まで。
URLﾘﾝｸ(ideone.com)
777:デフォルトの名無しさん
15/09/06 21:15:29.55 QKeqN0i2.net
>>729
URLﾘﾝｸ(ideone.com)
C++。ギブアップ。細かい仕様が対応できなかった。
表示回りっていつも適当だから、ここまで手の込んだのは無理やったわ。
GOTO使ってるあたりに苦悩を感じてくれ。
算数できなくなってることに絶望した。
778:デフォルトの名無しさん
15/09/06 23:58:23.31 3aEa3HTV.net
>>729 C
URLﾘﾝｸ(ideone.com)
原始的に配列へ詰め込んでソート、文字列の生成は断念した
779:デフォルトの名無しさん
15/09/07 03:04:02.94 QAzFwx2+.net
>>665 C
URLﾘﾝｸ(ideone.com)
780:デフォルトの名無しさん
15/09/07 03:04:53.70 QAzFwx2+.net
>>729 C
URLﾘﾝｸ(ideone.com)
781:デフォルトの名無しさん
15/09/07 03:43:16.07 hx62h88L.net
>>729 C
URLﾘﾝｸ(ideone.com)
782:デフォルトの名無しさん
15/09/08 00:20:53.77 qsWudAV2.net
>>729
省略の基点というのがよくわかりません
783:デフォルトの名無しさん
15/09/08 00:24:13.57 HV2JZhb0.net
>>748
SpotLightを中心点に表示を要求されるのでここを目印にDISP-2個位表示させるのが今回のお題。
784:デフォルトの名無しさん
15/09/08 05:55:05.13 byflMgx0.net
お題
ソート済み配列などに対し、falseを返すまで繰り返し適用することで
重複なく全順列を列挙できる破壊的操作を行う関数 next_permutation を
定義せよ。
文字列 "aaabc" に対する使用例（C++erはネタバレ注意）：URLﾘﾝｸ(ideone.com)
- 標準またはそれに準ずるライブラリに同等機能がある言語の場合は、その使用例を提示するだけでよい。
もちろん、自力での再実装にこだわってみるのもよい。
- 配列などに対し、その部分のみに適用できるようにはしなくてよい。
- 言語仕様で非破壊操作がしにくい言語の場合は、有限リストやストリーム、
ジェネレータなどを生成する実装に代えてもよい。
785:デフォルトの名無しさん
15/09/08 07:05:29.36 iUE7XWFn.net
>>750
×非破壊操作がしにくい → ○破壊操作がしにくい
786:デフォルトの名無しさん
15/09/08 10:54:06.55 n5Qbp6yS.net
>>750 Python3
引数を破壊的変更しないジェネレータ、要素がタプルになるのでfuncで加工する
import itertools
def next_permutations(seq, func=(lambda x: x)):
return map(func, sorted(set(itertools.permutations(seq))))
for a in next_permutations("aaabc", func=''.join):
print(a)
787:デフォルトの名無しさん
15/09/08 12:04:00.18 N3BcRQN+.net
ボードゲーム スカイゲスト
Miracle Five World Cup 〜 スカイゲスト
ミラクルファイブ今年に続いて、Othello World Cup 2014 でもミラクルファイブが正式競技として行われることが決まったようですね。
知ってる人は知っている、でもほとんどの人は知らないと思いますが、私、このスカイゲストの世界チャンピオンなんです。
ちなみに日本大会は現在三連覇しています。
で、残念なことに、現状ではネット上でこのスカイゲストをやれる環境が存在してないので、ささやかな興味を持ったとしても、
なかなか実際にプレイするところまでは行かないんですよね。だからそりゃぁ、なかなか普及してません。
そんなわけで(?)、ちょっとこのゲームのルールを軽く説明してみようかと。
URLﾘﾝｸ(www.othello.org)
URLﾘﾝｸ(blog.goo.ne.jp)
スカイゲストAIのアルゴリズム(評価関数編)
オセロの考案者である長谷川五郎氏が考案したボードゲームに、スカイゲスト(SkyGuest、テンゲストも同じルールっぽい)というものがあるのをご存知でしょうか？
大変面白いゲームなのですが、ネット上にこれをプレイできる環境がなかったので、AIを作成しました。
今のところ公開する予定はございませんが、ある程度の強さのものが出来上がったので、アルゴリズムの方を紹介したいと思います。
URLﾘﾝｸ(blog.livedoor.jp)
788:デフォルトの名無しさん
15/09/08 12:19:34.11 JhgINqf8.net
>>750 GNU Smalltalk
URLﾘﾝｸ(ideone.com)
789:デフォルトの名無しさん
15/09/08 12:48:53.12 JhgINqf8.net
>>752
Pythonって、すごくシンプルに書けて格好いいですね。
ただ、この実装だと、多要素だけど要素のほとんどが同じで簡単に返せる場合
（たとえば "aaaaaaaaaaaaaaaaaaaaaaaaaaaaab" とか）
にもかかわらず戻ってこなくなったりしませんか？
790:デフォルトの名無しさん
15/09/08 13:03:12.99 JcPY1iwa.net
>>750
C#
URLﾘﾝｸ(ideone.com)
791:デフォルトの名無しさん
15/09/08 16:46:37.82 HV2JZhb0.net
げ、パーミテーション自作してる人いるの。
すさまじいな。
俺C++の組み込みよく使うけど自作はさっぱりわからんぞ。
792:デフォルトの名無しさん
15/09/08 19:32:53.81 N3BcRQN+.net
パーミテーション=順列か。
順列生成くらいは入門レベルかと。速度は別にして。
どんな経験者だよ。
793:デフォルトの名無しさん
15/09/08 19:52:51.45 HV2JZhb0.net
数学
794:ダメなんですよ。ため息出るわ。
795:デフォルトの名無しさん
15/09/08 19:59:30.98 MMxN10T7.net
俺は数学、足し算なら怖くないな。
ただし演算数、非演算数、ともに二桁以内な
796:デフォルトの名無しさん
15/09/08 20:35:18.17 WO1DF9qJ.net
C++のnext_permutation()アルゴリズムのヘッダを見て真似するのが一番簡単
797:デフォルトの名無しさん
15/09/08 20:59:28.34 MMxN10T7.net
バカにしてたけど
javaやることにした
とりあえず スッキリわかるジャバジャバのKindle版注文した
ん？スレチだな
(*´σｰ｀)ﾍﾍﾍ
798:デフォルトの名無しさん
15/09/09 01:01:53.28 WxXYPcUn.net
N=1 一意解=1 全解=1
N=2 一意解=0 全解=0
N=3 一意解=0 全解=0
N=4 一意解=1 全解=2
N=5 一意解=2 全解=10
N=6 一意解=1 全解=4
N=7 一意解=6 全解=40
N=8 一意解=12 全解=92
N=9 一意解=46 全解=352
N=10 一意解=92 全解=724
N=11 一意解=341 全解=2680
N=12 一意解=1787 全解=14200
N=13 一意解=9233 全解=73712
N=14 一意解=45752 全解=365596
N=15 一意解=285053 全解=2279184
799:デフォルトの名無しさん
15/09/10 00:08:40.35 kopU2pqH.net
GCJはプログラミングコンテスト本が出てるのでProject Eulerで
URLﾘﾝｸ(projecteuler.net)
でも"project euler solutions 99"なんかでぐぐったら駄目ですよ
まあ似たようなコードになると思うけど
2^11と3^7のような指数形式で書かれた2つの数を比較するのは難しくありません
しかし、632382^518062＞519432^525806であるのを確認するのは300万桁を超える
数字を含んでいるのではるかに困難でしょう
base_exp.txt(問題文をクリックしてください)は1000行を含む22KBのテキストで、
それぞれの行に基数と指数が対になっています
どの行の数が最大になるか決定してください
注：ファイル注の最初の二行は上記の例に示されたものです
800:デフォルトの名無しさん
15/09/10 00:10:08.60 kopU2pqH.net
あ、忘れました
お題です
801:デフォルトの名無しさん
15/09/10 00:33:27.38 AxUmdUI6.net
n T U [cost]
1 1 1 (0[msec])
2 0 0 (0[msec])
3 0 0 (0[msec])
4 2 1 (0[msec])
5 10 2 (0[msec])
6 4 1 (0[msec])
7 40 6 (0[msec])
8 92 12 (0[msec])
9 352 46 (0[msec])
10 724 92 (16[msec])
11 2680 341 (0[msec])
12 14200 1787 (94[msec])
13 73712 9233 (499[msec])
14 365596 45752 (3011[msec])
15 2279184 285053 (19843[msec])
16 14772512 1846955 (140806[msec])
ネット回線からの割り込みが多かったので
コストは参考値
802:デフォルトの名無しさん
15/09/10 04:21:19.51 hMjmDO5x.net
>>763
>>766
>>1
803:デフォルトの名無しさん
15/09/10 05:17:03.70 2byHSaL/.net
>>750 Python3
関数の仕様を勘違いしていたのでやりなおし
>>755の指摘を参考に要素に重複があるとき計算を省略する
def next_permutations(iterable):
orig = tuple(iterable)
def recursive(seq, acc):
if not seq:
yield acc
elif orig[:len(acc)] <= acc:
for v in sorted(set(seq)):
newseq = seq[:]
newseq.remove(v)
yield from recursive(newseq, acc+(v,))
return recursive(list(iterable), ())
for a in next_permutations("aaabcaaabcaaabc"):
print(''.join(a))
804:デフォルトの名無しさん
15/09/10 11:55:20.61 0vTqxZ6A.net
>>768
すばらしい。GNU Smalltalk に移植してみました。（文字列のみ対応の手抜きで恐縮ですが…）
URLﾘﾝｸ(ideone.com)
805:デフォルトの名無しさん
15/09/10 21:31:45.79 AToafzam.net
>>729 c
URLﾘﾝｸ(ideone.com)
806:Fcc
807:デフォルトの名無しさん
15/09/10 22:15:18.95 Q2vaRfqD.net
>>764
モロにカンニングですみませんが
URLﾘﾝｸ(ideone.com)
808:デフォルトの名無しさん
15/09/11 01:59:58.81 0Pjc40Dt.net
>>652 遅ればせながらPerl
use 5.016;
use List::Util 'sum';
say sum grep {$_ % 5 == 0 or $_ % 3 == 0} 1..1000;
809:デフォルトの名無しさん
15/09/11 21:51:13.27 v7E2xSv/.net
手抜きPerl
use 5.016;
sub next_permutations {
my %h;
sub fn {
my ($l, $p, @r) = @_;
defined $p ? map {[$p, @$_]} fn([], @$l, @r) : ([])
,
@r ? fn([@$l, $p], @r) : ()
}
map {$h{$_} = 1} keys {map {join('', @$_) => 1} fn [], @_};
keys %h
}
say for next_permutations split '', 'aaabc';
810:デフォルトの名無しさん
15/09/11 22:39:05.52 v7E2xSv/.net
use 5.016;
sub next_permutations {
sub fn {
my ($l, $p, @r) = @_;
defined $p ? map {[$p, @$_]} fn([], @$l, @r) : ([])
,
@r ? fn([@$l, $p], @r) : ()
}
keys {map {join('', @$_) => 1} fn [], @_};
}
say for next_permutations split '', 'aaabc';
これでええやん、つか破壊してないし、過剰仕様
しっか〜くｗ
811:デフォルトの名無しさん
15/09/12 14:21:20.66 9MDXYKkO.net
>>774
元の並びがソートされている場合、
保持されている現在の並びを破壊しながらでも
ジェネレータみたいに呼び出される度に次の順列を
重複なく返すアルゴリズムが>750のお題の肝では？
812:デフォルトの名無しさん
15/09/13 19:11:57.62 dr5xNYTR.net
>>775
お題に「生成される順列はソートせずとも辞書順に並ぶこと」って一言いれておけばよかったですね^^;
813:デフォルトの名無しさん
15/09/13 20:57:12.14 bLikZ+wL.net
>>750 OCaml
URLﾘﾝｸ(ideone.com)
引数はリスト限定で破壊的操作はしない、返り値で次の順列を返す
814:デフォルトの名無しさん
15/09/13 22:52:40.22 b32GJr7l.net
>>441 c
URLﾘﾝｸ(ideone.com)
注：肝心な部分（comb, permute）はぐぐったサイトから無断で拝借しました
815:デフォルトの名無しさん
15/09/14 07:17:09.48 aQticbJR.net
>>778
中身が見えない
816:デフォルトの名無しさん
15/09/14 20:25:46.47 Gwz4vSRg.net
>>441 c
URLﾘﾝｸ(ideone.com)
>>778からの変更点：
・いったん全パターンもつのをやっぱやめる
・細部のちょこちょこっとした改善
817:デフォルトの名無しさん
15/09/15 21:30:13.30 jovL9vh0.net
>>775 うっせーな、ハゲっが。
「生成される順列はソートせずとも辞書順に並ぶこと」の意味が
「出力する行がsort済みの順番に並んでいる」順列という意味ならこうか：
use feature qw{:5.16};
use Data::Dump qw(dump);
sub next_permutation {
defined $_[1] and next_permutation(@_[1..$#_]) or
($_[0] lt $_[1]) and
do {
do {$i = $_
if $_[0] lt $_[$_]}
for 1..$#_;
@_[0, $i] = @_[$i, 0];
@_[1..$#_] = sort @_[1..$#_];
1 }
}
#@a = split '', 'aaabcaaabcaaabc'; # ←この入力はカラムがsort済みじゃねーしw
@a = split '', 'aaabc';
say join '', @a;
say join '', @a while next_permutation @a;
出力行ごとのカラムもソートされているという制限つきの順列生成なら
中のdoがif産業が一行になるかな。
つか、中のdo forも無名再帰で書くのがホンとは漢つーもんょ。
818:デフォルトの名無しさん
15/09/15 21:35:00.71 jovL9vh0.net
いや、ちょとまて
入力行一行のカラムがソートされてたら、
出力行のカラムもソートされているという制限をつけたら
出力順列は入力と同じたった一行しか存在しない、
ふー危うくひっかかるところだったぜ。
つーことで上の方のほかの人の回答に間違っているのない？
819:デフォルトの名無しさん
15/09/15 21:46:18.62 jovL9vh0.net
やっぱほかの人の解も合ってるかな？
よく見てないけどｗ
'aaabcaaabcaaabc';の入力の並びに目が惑わされたワイ
じゃーな、ハゲっが。
820:デフォルトの名無しさん
15/09/15 22:10:44.77 jovL9vh0.net
>>781 連投ごめんなさい、or式全体を()でくくらないと出力に抜けが起きるバグありあした…orz
修正版：
use feature qw{:5.16};
sub next_permutation {
defined $_[1] and (next_permutation(@_[1..$#_]) or
($_[0] lt $_[1]) and
do {
do {$i = $_
if $_[0] lt $_[$_]}
for 1..$#_;
@_[0, $i] = @_[$i, 0];
@_[1..$#_] = sort @_[1..$#_];
1 })
}
#@a = split '', 'aaaaaaaaaaaaaaaabc';
@a = split '', 'aaabc';
say join '', @a;
say join '', @a while next_permutation @a;
821:デフォルトの名無しさん
15/09/16 00:38:04.82 zgtxEZCv.net
>>784
左側の新しい項の入れ替えに移行し右側の並びを一式リセットするためのsortは
reversieでよいはず。これにより並べ替えのオーダーをNloｇNからNに低減できる。
また項を入れかえる対象の要素を検索する繰り返しは、その項より大きくかつ最も小さい
値の要素を探すので、平均行程1/2で打ちって検索の計算量も半減することができる。
それから、もう少しコンパクトかつ可読性ある書き方ができるはず。
822:デフォルトの名無しさん
15/09/16 00:59:37.85 NuZWJDts.net
>>16 c
URLﾘﾝｸ(ideone.com)
カウント版と算出版と両方
カウント版で出した値じっくりながめると
9, 99, 999…っていう値の気配がしたので
それ中心に押したり引いたりしながら算出
なお、理屈はよくわかっていないもよう
823:デフォルトの名無しさん
15/09/16 01:04:42.91 zgtxEZCv.net
use feature qw{:5.16};
sub next_permutation {
defined $_[1] and (next_permutation(@_[1..$#_]) or
($_[0] lt $_[1]) and
do {
for (1..$#_)
{$_[0] lt $_[$_] ? $i = $_ : last}
@_[0, $i] = @_[$i, 0];
@_[1..$#_] = reverse @_[1..$#_];
1 })
}
#@a = split '', 'aaabc'; # 'aaaaaaaaaaaaaaaabc';
@a = split '', '112334556';
say join '', @a;
say join '', @a while next_permutation @a;
こんな感じな。sortをreverseにしたとき、ぐっと速くなった。
824:デフォルトの名無しさん
15/09/16 05:12:59.25 TSIOTapp.net
>>750 Ruby
URLﾘﾝｸ(ideone.com)
825:デフォルトの名無しさん
15/09/16 07:10:31.01 2Yj1o+46.net
>>750 Go
URLﾘﾝｸ(ideone.com)
Permutationインターフェースを実装すれば他の型でもできる
826:デフォルトの名無しさん
15/09/16 13:06:36.59 fQczy5Yc.net
ruby初心者スレでこちらに書く様に促されたので、
できればrubyかpythonで答えて頂けるとありがたいです。
お題
以下の様な数値群から、重複しない要素を使って任意の数値(例えば2360)に最も近い和を求めるにはどうしたら良いでしょう?
115,135,215,352,358,655,885,925,936,1250,1285,1620,1850
827:デフォルトの名無しさん
15/09/16 14:20:54.79 VfqLXb9I.net
115+135+215+358+655+885=2363
828:デフォルトの名無しさん
15/09/16 14:23:48.16 aL/dguIa.net
>>791
任意の数値のアルゴリズム
829:デフォルトの名無しさん
15/09/16 15:06:27.46 VfqLXb9I.net
データ件数10000件の場合とかだなｗ
830:デフォルトの名無しさん
15/09/16 16:09:16.80 9fL6Ueyi.net
ポテトチップスを、60gの袋詰めする機械では、
9個の秤に、幾らかのポテトチップスが載っていて、
その秤の中から、60g以上で、
最も少ない重さを計算して、袋詰めする
9個の秤の重さの合計を、sum9として、
1個の秤の重さを求めると、残り8個の秤の重さもわかる。
2個の秤の重さを求めると、残り7個の秤の重さもわかる。
3個の秤の重さを求めると、残り6個の秤の重さもわかる。
4個の秤の重さを求めると、残り5個の秤の重さもわかる
831:デフォルトの名無しさん
15/09/16 16:44:57.70 9fL6Ueyi.net
重複を許さない組合せ
Array.combination
13個の数字の合計を、sum13として、
1個の数字を求めると、残り12個の数字の合計もわかる。
2個の数字の合計を求めると、残り11個の数字の合計もわかる。
.
.
6個の数字の合計を求めると、残り7個の数字の合計もわかる
つまり、6個までのすべての組合せを計算すればよい
832:デフォルトの名無しさん
15/09/16 17:54:44.06 slZMIjby.net
>>790
> 以下のような
っていう部分はどう解釈すればいいの？
例に挙がってる程度の数であれば、
総当りでいいんじゃね？
これ↓と同質の問題ならリンク先を参照。
URLﾘﾝｸ(ja.wikipedia.org)
833:デフォルトの名無しさん
15/09/16 18:58:52.94 saSs2l+c.net
>>790 ruby 2.0.0
単に全パターンをチェックした場合
def f789(a, target)
combos = (1..a.size).inject([]) {|r, i| r += a.combination(i).to_a}
min = combos.min_by {|combo| (target - combo.inject(:+)).abs}
[min, min.inject(:+)]
end
p f789([115,135,215,352,358,655,885,925,936,1250,1285,1620,1850], 2360)
↓
[[115, 135, 215, 352, 655, 885], 2357]
834:デフォルトの名無しさん
15/09/16 20:10:54.59 aL/dguIa.net
データの方も任意なんだろう。「ような」が付いてる。
> 以下の様な数値群
835:デフォルトの名無しさん
15/09/16 20:53:50.13 ExTMGHGk.net
>>790
URLﾘﾝｸ(ideone.com)
一応解いたがオセー。最新CPUで1：40かかる。
順列使うくらいなら再起使ったほうが早いな。
コンビネーションほしー。
836:デフォルトの名無しさん
15/09/16 22:16:07.44 JeX5l5vV.net
>>790
データの数が20個程度なら総当りで問題なく解けそうだけど最大数いくつ？
837:デフォルトの名無しさん
15/09/16 22:42:12.73 aL/dguIa.net
これでいいのでは? データがx0, x1, ・・・xN、yに近い和を求めるとして。
y = xnとなるnがあれば終了。
そうでないとき、y > xnとなる最大のnについて、次の値でいいやつを選べはいいのでは?
x(n+1) // yより大きくもっとも近い値
cal (y, {x0, ・・・x(n-1)}) //和にxnを含まないときの最良値
cal (y-xn, {x0, ・・・x(n-1)}) //和にxnを含むときの最良値
838:デフォルトの名無しさん
15/09/16 22:53:06.43 aL/dguIa.net
>>801で関数calを作ればいい。
cal(y, vec)とすると、y,かvecが小さくなるので再帰関数で作れるはず。
839:デフォルトの名無しさん
15/09/16 23:59:55.71 JeX5l5vV.net
>>790
URLﾘﾝｸ(ideone.com)
とりあえず何も考えずに総当り
20個だと1秒くらいで出るけど数が増えると死ぬ
840:デフォルトの名無しさん
15/09/17 00:21:00.74 56vB2llc.net
網羅するしかないけど、再計算はしない、大きすぎる・小さすぎる和を検出して無駄なループをさせない点がポイントでは。
841:デフォルトの名無しさん
15/09/17 00:36:51.76 oSu48zpr.net
>>790
URLﾘﾝｸ(ideone.com)
前に書えたやつを軽く修正
全探索解(2^n*n)と、ウソDP解(n*最大重量)
基本python2.xだけど、pypyで実行
842:789
15/09/17 08:46:22.84 aStCI4Gl.net
解答してくださったみなさんありがとうございます。
元々は50程度の数値群で、別にやらなきゃいけない物でもなかったんですが、
プログラミングでやるとしたらどうやるのかなと思ったのですが、
自分では解法が考えつかなかったので書き込んでみました。これから少しずつ見て理解してみます。
843:デフォルトの名無しさん
15/09/17 09:19:36.19 7rI3c1r5.net
>>790 OCaml
URLﾘﾝｸ(ideone.com)
力任せ探索をハッシュテーブルを使ってメモ化
844:名無しさん＠お腹いっぱい。
15/09/17 11:24:35.90 Ref/prt+.net
今度ＰＳ４が値下げするそうなんだけど
ＰＳ４でプログラミングはできるのかな？誰か教えて。
ＣとかRubyとかその他。
845:デフォルトの名無しさん
15/09/17 13:03:14.26 56vB2llc.net
PS4単体でプログラミングできる仕組みはあるのかしらないけど。
PS4で動くソフトの開発は素人でもできるのでは?
PS4で動くコンパイラとかエディタとかキーボードとか揃えばできるとおもうが。
846:デフォルトの名無しさん
15/09/17 13:08:21.98 56vB2llc.net
適当にかいた。ここには契約しないとできない
847:となってる。個人利用でもソニーから開発環境提供してもらわないとムリなのか? PlayStationRソフトウェアの提案・開発・発売をしたい | PlayStation.com https://support.jp.playstation.com/app/answers/detail/a_id/161
848:名無しさん＠お腹いっぱい。
15/09/17 13:18:09.20 Ref/prt+.net
ＰＳ４の使い道があまりないのでＰＣ代わりにプログラミングの勉強に使えないかと
思ったが、やっぱりダメみたいだね。
普通にＷＩＮＤＯＷＳ ＰＣを使う事にするよ。
回答ありがとう。
849:デフォルトの名無しさん
15/09/17 13:59:14.02 56vB2llc.net
>>806
やってないけど50個は手強いかと。
総当りだと、2^50 = 1125899906842620とおりで普通のPCでは計算終わらないはず。
工夫したとしても手強いはず。
850:デフォルトの名無しさん
15/09/17 14:06:34.37 56vB2llc.net
確実で最初にやるといいと思える計算削減法は。
たとえば101を生成したいとき、101がデータにあるならばそれを使えばよく、それ以下の和で101を生成すべきではないな。
これは事前に検出しておいたほうがよさげ。
851:デフォルトの名無しさん
15/09/17 17:42:20.70 IC3slnA5.net
求める値が10000( > 2360 * 50 / 13)程度なら、>>805これのfunc1で行ける
852:デフォルトの名無しさん
15/09/20 05:58:43.13 vBjKt0IW.net
「Googleの入社試験」より
正の整数 n が与えられたとき、
0からnの間の、すべての整数に使われている、
1の数を返す関数 f があります
例えば、f(1) = 1; f(13) = 6 など。
今、nが2以上で、f(n) = n となる最小のnを求めよ
参考までに、
f(99) = 20; f(999) = 300; f(199,999) = 200,000
答え、n = 199,981
853:デフォルトの名無しさん
15/09/20 08:06:14.95 f/DwOlJx.net
>>815
「10進法表記で」かい？
854:デフォルトの名無しさん
15/09/20 08:25:53.78 g7ao8Sb7.net
>>815
URLﾘﾝｸ(ideone.com)
C++。とりあえず2通り書いてみたけど、どっちも遅い。
片方は並列化すれば多少早くなるはず。片方はデバッグ投げた。コンビネーションほしい。
最近まともに解けてないな・・・。
855:814
15/09/20 08:37:04.35 vBjKt0IW.net
>>816
もちろん、10進数だよ
f(13) = 6
1, 10, 11, 12, 13で、1を6個使っている
11は、2個で数える
856:デフォルトの名無しさん
15/09/20 09:36:23.85 1JwuQWhK.net
入社試験でパソコン使っていいのか？
857:デフォルトの名無しさん
15/09/20 10:45:18.64 7mBXEM/X.net
>>815 OCaml
URLﾘﾝｸ(ideone.com)
最小のnのみ表示、経過はアウトプットしてない
858:デフォルトの名無しさん
15/09/20 12:10:16.54 4gyZNSF5.net
>>815 C
URLﾘﾝｸ(ideone.com)
859:780
15/09/20 13:29:55.06 Ac94krKF.net
>>815
use feature qw{:5.16};
sub f1 { # 0..10**$d - 1 (0..999など)の間にある総和
my $d = shift;
my $i = 10**$d;
my $n = ($i / 10) * $d;
($i, $n) }
sub f2 { # 0..10**$d *2) (0..2000など)最上位が2になるまでの間にある総和
my $d = shift;
my $i = 10**$d * 2;
my $n = $i / 2 + ($i / 10) * $d;
($i, $n) }
my $o = 2;
do {
($i1, $n1) = f1 $o;
($i2, $n2) = f2 $o;
say "$o: $i1..$i2, $n1 ~ $n2";
$o++;
} while $n2 < $i2;
$ perl 7_814_0.pl
2: 100..200, 20 ~ 140
3: 1000..2000, 300 ~ 1600
4: 10000..20000, 4000 ~ 18000
5: 100000..200000, 50000 ~ 200000 ← 解はこの間にある
理屈で考えると、最上位桁が1以外の0,2..9の場合はその値までの文字1の総和は
値に漸近しないので、解は最上位が1となる１xxxx ... 1999...の間にある筈。
上記はそれを確認したコード、この考えに基づき再帰的探査で速やかに見つからないかな…
時間があったらやってみたいが引越しの準備で…、ハゲっが。
860:デフォルトの名無しさん
15/09/20 14:17:21.30 W3KPe91F.net
>>815 c
URLﾘﾝｸ(ideone.com)
861:デフォルトの名無しさん
15/09/20 22:12:07.71 w687FJud.net
>>815 Squeak/Pharo Smalltalk
| g f m |
g := [
| memo |
memo := OrderedCollection with: 1.
[:n |
n - memo size timesRepeat: [
memo add: (memo last + ((memo size + 1) asString occurrencesOf: $1))].
memo at: n
]
].
f := g value.
m := 1.
[(m := m + 1) = (f value: m)] whileFalse.
^m "=> 199981 "
862:デフォルトの名無しさん
15/09/20 22:53:09.92 g7ao8Sb7.net
高速化しようとしてthreadいじってみたけど、そっちの闇にのまれて全く進まなかった。Orz
真面目に最後までやって終わってるのかすらわからん・・・。
863:デフォルトの名無しさん
15/09/20 23:01:38.16 D6HrfyQE.net
マンカラ= カラハ = 豆まきゲームのAI作成で。自分が強いのを作るので対戦。
マンカラ ( ボードゲーム ):無料Flashゲーム
URLﾘﾝｸ(www.sousakuba.com)
ゲーム「カラー」の説明
それでは、例題として取り上げるゲーム「カラー (Kalah) 」を説明します。
このゲームはルールこそ単純ですが、展開がスリリングで面白いゲームです。
URLﾘﾝｸ(www.geocities.jp)
864:デフォルトの名無しさん
15/09/20 23:15:14.16 7mBXEM/X.net
>>822の検証をしていたら
9が並んだパターンのnは、1の数え上げが不要なことが分かった
下のPython3のコードはnの桁の数から>>815のf(9...9)の場合の値を出してる
import math
def f_9x(n):
a = math.floor(math.log10(n))
return (a+1) * pow(10, a)
f_9x(9) # 1
f_9x(99) # 20
f_9x(999) # 300
f_9x(9999) # 4000
f_9x(99999) # 50000
f_9x(999999) # 600000
865:780
15/09/20 23:55:39.69 Ac94krKF.net
>>827
ｺﾞﾒﾝチャイ
>>822は間違いがあって
× 最上位桁が1以外の0,2..9の場合はその値までの文字1の総和は値に漸近しない
○ ある値における最上位桁から現在着目している桁までの間に1がない場合は
その値を右にインクリメントしていっても、文字1の総和は値に漸近しない
たとえば
xxxxxxxxxxooooooooooxxxxxxxxxxx o o x o
1…1…2…2
0000000000111111111122222222223…0…1…0…1
0123456789012345678901234567890…0…0…0…0 ←着目している桁
図で書くとxのことろに解はなく、oのところに解がある可能性がある
これ2,3桁なのでちょっと分かりにくいかもしれないけど、桁数が多場合を考えると分かりやすいかも
で、その考えに基づいて速やかに解に近づくようなcodeを書こうと
思ったけど、結構骨が折れてまだ完成しないｗ
866:780
15/09/21 01:39:22.93 jBw1B4c/.net
>>815 Perl
こった解探索ｱﾙｺﾞﾘｽﾞﾑの物はすぐできない感じなので、
愚直に1から探していくﾊﾞｰｼﾞｮﾝをまずは…
use feature qw{:5.16};
($s, $_) = (1, 1);
do {
$_++;
$s += (() = /1/g);
} while $s < $_;
say $_;
$ perl 7_814_x.pl
199981
867:デフォルトの名無しさん
15/09/21 01:53:22.45 j5q7sFQh.net
1を数えるのはそんなに難しそうになくプログラムもなくても出来ないのか?
10区切りで1のケタをみれば、1個しかなくこれがループしてるだけ。
10の位も100の位も似たようなもので精密に数えたら手計算でもできないか?
868:デフォルトの名無しさん
15/09/21 02:12:51.56 GyvZP+14.net
論よりコード。
869:780
15/09/21 02:17:07.55 jBw1B4c/.net
>>830
ある切のいい値、たとえば100とか2000-1とかまでだと机上計算でもすごく簡単なの。
下記はその筆算イメージをcode化したもの、
use feature qw{:5.16};
for ($o = 2; ; $o++) {
$i1 = 10**$o;
$n1 = ($i1 / 10) * $o;
#$i1--; # fix
$n1++;
$i2 = 10**$o * 2;
$n2 = $i2 / 2 + ($i2 / 10) * $o;
$i2--; # fix
say "$o: $i1..$i2, $n1 ~ $n2";
last if $i2 <= $n2;
}
$ perl 7_814_1.pl
2: 100..199, 21 ~ 140
3: 1000..1999, 301 ~ 1600
4: 10000..19999, 4001 ~ 18000
5: 100000..199999, 50001 ~ 200000
これを発展させる形で、切の悪い値も、解の候補の可能性があるものを渡り歩いて
速やかな>815の求解プログラムとするには
モレ的にはもう少し方式検討が要る感じがして、>829で一旦 日和らせてもらた
870:780
15/09/21 02:30:00.52 jBw1B4c/.net
>>832
この弱点は、ある値が与えられたら、1からその値までの文字1の総和を
解析的にというか式で算出することに気がとられ、
そのような計算式にもとづき、切の悪い値の中にある>815の求解に挑む
方向に考えが流されちゃったところかな。
発想を転換した方が良いかもしれないと思った。
和を足し込みながら漸近させて行く方法などと組み合わせるとかね。
さ、寝るわ。
871:デフォルトの名無しさん
15/09/21 03:09:20.39 TV+aglfl.net
>>815
愚直に日本語
0. s=0とする
１．n=0
2. nを１０進数であらわしたときに含まれる1の数
を数えそれをdとおく
3. k=0,...9として
4. k=1のときはd+1,それ以外をsに足しn+kに一致したら
出力して終了
5. 3のループを継続
6. n=n+10として1.へ
2.の処理の詳細
d=0;m=n;while(m){ d=(m % 10==1)?1:0; m/=10;}
愚直で効率が悪いのでＣで書いても100m秒もかかって
しまった。
872:訂正
15/09/21 03:10:53.01 TV+aglfl.net
４．k=1のときはd+1,それ以外はdをsに足し、sがn+kに一致したら
出力して終了(n+k<2の場合は継続)
873:またもや訂正（スマンコ)
15/09/21 03:12:02.29 TV+aglfl.net
6. n=n+10として2.へ
874:デフォルトの名無しさん
15/09/21 08:29:38.04 K1QACkp5.net
>>831
>論よりコード。
超名言w
875:デフォルトの名無しさん
15/09/21 08:35:28.97 OcjZ8RWa.net
いいね
論よりコード
876:デフォルトの名無しさん
15/09/21 09:05:31.09 QVf3KibQ.net
これは良い。テンプレに入れようず
877:デフォルトの名無しさん
15/09/21 11:10:04.89 K1QACkp5.net
>>815
@Mathematica
URLﾘﾝｸ(ideone.com)
※ナイーブに書き下したので、2時間経っても計算が終わらない orz
878:デフォルトの名無しさん
15/09/21 11:47:33.16 TV+aglfl.net
Ｃ語で書き直し
[?]には整数型変数名を入れてください
#include <stdio.h>
static int odai814(void){
int [?]=0,[?]=0,[?],[?],[?];for(;;[?]+=10){[?]=[?],[?]=0;
while([?])[?]+=(([?]%10)==1)?1:0,[?]/=10;
for([?]=0;[?]<10;[?]++)if(([?]+=([?]==1)?[?]+1:
[?])==[?]+[?])if([?]+[?]>1)
return [?]+[?];}}
int main(void) {printf("%d\n",odai814());return 0;}
879:デフォルトの名無しさん
15/09/21 12:17:20.21 zZoSoqbh.net
>>815のnと1の総数の関係が少し面白くて、お題とはちょっとず
880:れるけど f(n)=nとなるnを全て計算してみました >>827を見るとnの桁数が大きくなると1の総数f(n)がnを追い越すことから 有限個と予想はできるのですが、実際計算してみるとf(n)=nとなる数は 0,1を入れると84個っぽい C言語：http://ideone.com/6jwkpQ
881:780
15/09/21 12:39:31.93 jBw1B4c/.net
>>842
面白い結果だね。
13:[200000]
25:[2600000]
28:[35000000]
40:[35200000]
などは一旦 f(n)>n と逆転したあとに、f(n)==nに戻ったところだね
882:デフォルトの名無しさん
15/09/21 13:22:00.66 o5zq47rX.net
>>815 Emacs Lisp
(require 'cl-lib)
cl-lib
(defun f (n &optional m)
(if m (+ m (cl-count ?1 (format "%d" n)))
(cl-loop for i from 0 to n sum (cl-count ?1 (format "%d" i)))))
f
(f 1) 1
(f 13) 6
(f 99) 20
(f 999) 300
(f 199999) 200000
(let* ((n 2) (sum (f (1- n))))
(cl-loop (when (= (setq sum (f n sum)) n) (return n)) (incf n)))
199981
883:デフォルトの名無しさん
15/09/21 14:13:32.12 vwg3dHwd.net
数字1の出現を見抜けるかどうかか
Google問題は
ヒントを知ると容易
ヒントが無ければ、f(1)=1, f(13)=6で一生悩む
>>842
深いな
884:780
15/09/21 16:14:22.83 jBw1B4c/.net
>>833 >815 のお題で1の出現回数を0から足し込んでいくのではなく
ある値が与えられたら、0からその値までの間に出現する1の個数を式で一気に求めることができた。
言語：perl
use feature qw{:5.16};
sub fn {
my ($o, $w, $s) = (0 x 3);
my $d = shift;
if (defined $d) {
$s = fn(@_);
$o = scalar @_; # aboid $#_ problem
$w = 10**$o;
$s += $d * $o * $w / 10
if $o > 0;
if ($d > 1) {
$s += $w;
} elsif ($d == 1) {
$s += 1 + join '', @_; # `1 +' means including 0
}
#say "$d, $o, $w: $s";
}
$s
}
@vals = qw{1 10 11 13 99 100 110 111 199 200 999 1000 19999 199980 199981 199982};
say "$_ : ", fn(split '', $_)
for @vals;
885:780
15/09/21 16:16:19.84 jBw1B4c/.net
>>846 の実行例（行が多すぎたので2レスに分割）
$ perl 7_814.pl
1 : 1
10 : 2
11 : 4
13 : 6
99 : 20
100 : 21
110 : 33
111 : 36
199 : 140
200 : 140
999 : 300
1000 : 301
19999 : 18000
199980 : 199979
199981 : 199981
199982 : 199982
あとは解の候補があり得る値の所を飛び飛びで上手にわたって行くようなmainを作ることができれば、
0から足し込んで探すナイーブな解法に対し、演算量を劇的に低減できるかもしれない。
時間があったらやって見ますﾜ
次ページ最新レス表示スレッドの検索類似スレ一覧話題のニュースおまかせリスト▼オプションを表示暇つぶし2ch
627日前に更新/308 KB
担当:undef