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

**デフォルトの名無しさん** · 2019/07/28(日) 19:39:57.54

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

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

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

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

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

>>257 Java
https://ideone.com/4I2YQt

**デフォルトの名無しさん** · 2019/09/01(日) 19:32:51.46

>>257 Perl5

$n = 24;
@a = map{int rand 255} 1..$n;;
print "@a\n";
@b = map{sprintf'%08b', $_} @a;
$" = '';
print "@b\n

実行例
~ $ perl 15_257.pl
155 105 94 58 85 82 124 6 242 94 119 175 69 205 95 25 79 154 237 248 169 254 46 93
100110110110100101011110001110100101010101010010011111000000011011110010010111100111011110101111010001011100110101011111000110010100111110011010111011011111100010101001111111100010111001011101

**デフォルトの名無しさん** · 2019/09/01(日) 19:42:33.97

>>257 Common Lisp
https://ideone.com/EmGPSF

**デフォルトの名無しさん** · 2019/09/01(日) 20:53:53.13

>>259
rand 255 ⇒ 256 の方がﾖｶﾀ

**デフォルトの名無しさん** · 2019/09/01(日) 21:45:06.97

>>259 ｺﾋﾟﾍﾟミス
print "@b\n
↓
print "@b\n";

**デフォルトの名無しさん** · 2019/09/02(月) 02:56:48.97

>>120

>>125 みたいに、1桁になるまでの変化の様子もリストで渡すようにした。

Haskell

main = mapM put [4,15,93,77,123,277777788888899]

put x = (putStrLn.concat) [show x," -> ",show a,
" loop and value is ",show n,". list = ",show l]
where (l,a,n) = f [] 0 x

f l a n| n < 10 = (reverse l,a,n)
f l a n = f (m:l) (a + 1) m
where m = product [read [x] | x <- show n]

**デフォルトの名無しさん** · 2019/09/02(月) 02:57:17.93

out:

4 -> 0 loop and value is 4. list = []
15 -> 1 loop and value is 5. list = [5]
93 -> 3 loop and value is 4. list = [27,14,4]
77 -> 4 loop and value is 8. list = [49,36,18,8]
123 -> 1 loop and value is 6. list = [6]
277777788888899 -> 11 loop and value is 0. list = [4996238671872,438939648,4478976,338688,27648,2688,768,336,54,20,0]

**デフォルトの名無しさん** · 2019/09/02(月) 06:37:20.55

>>257 Ruby

n = 16
x = Array.new(n){rand(0x100)}
b = n.times.reduce(0){|s, i| x[~i] * 0x100**i + s}

puts "%p => %0#{n}b" % [x, b]

# => [31, 95, 43, 108, 105, 54, 1, 122, 100, 48, 137, 121, 131, 188, 105, 244] =>
11111010111110010101101101100011010010011011000000001011110100110010000110000100010010111100110000011101111000110100111110100

**デフォルトの名無しさん** · 2019/09/02(月) 06:39:28.02

typo

puts "%p => %0#{n * 8}b" % [x, b]

# => [31, 95, 43, 108, 105, 54, 1, 122, 100, 48, 137, 121, 131, 188, 105, 244] =>
00011111010111110010101101101100011010010011011000000001011110100110010000110000100010010111100110000011101111000110100111110
100

**デフォルトの名無しさん** · 2019/09/02(月) 12:10:04.08

>>233
勉強になりましたｗ

**デフォルトの名無しさん** · 2019/09/02(月) 12:49:28.87

>>257
https://ideone.com/L5lkiU
C++。気が向いたのでstd::byte動かしてみたけど、ideonが対応してなくてグレードダウンした・・・。

**デフォルトの名無しさん** · 2019/09/02(月) 15:10:33.79

全滅エンドか！？

**デフォルトの名無しさん** · 2019/09/02(月) 21:31:28.92

>>247
VB
https://paiza.io/projects/ij82oWiswOxWM0VnAgVbWQ

**デフォルトの名無しさん** · 2019/09/03(火) 02:08:35.68

>>228
aa=$(echo ^{1..9}\\\{1,\\\}\$\\\| |sed -e "s/ //g; s/\\\|$//;"); seq 1 $((10**8)) |grep -e "$aa"

**デフォルトの名無しさん** · 2019/09/03(火) 03:13:14.41

数学的な解き方わからず
このx>=3の自然数解を見つける

a>b、　(a^2 - b^2)^x + (2ab)^y = (a^2 + b^2)^z

**272** · 2019/09/03(火) 05:28:10.06

a=2 b=1で　3^x + 4^y = 5^z
は解無し

**デフォルトの名無しさん** · 2019/09/03(火) 08:27:27.03

a b は実数？正の整数？

**デフォルトの名無しさん** · 2019/09/03(火) 08:38:58.69

出てくる文字、a b x y z はすべて自然数、正の整数です

**デフォルトの名無しさん** · 2019/09/03(火) 08:39:49.44

a > b > 0 なの？
0 > a なら意味ないんだけど
出題者が問題をそもそも理解してなさそう

**デフォルトの名無しさん** · 2019/09/03(火) 08:44:26.60

すべて1以上の整数として、
x>=3、　　a>b、　　(a^2 - b^2)^x + (2ab)^y = (a^2 + b^2)^z
を満たすものを見つける

そこでa=2 b=1の場合は解無しがわかっていて
任意のa,bに対して、(a^2 - b^2)^2 + (2ab)^2 = (a^2 + b^2)^2　が成り立つことも判っています

**デフォルトの名無しさん** · 2019/09/03(火) 08:57:07.87

指数2だと必ず成立するのはこれだからです
指数3以上で解けるのはどれか、あるかです

ピタゴラス数は無数にある
中学校の数学で習う定理に、「三平方の定理」或いは「ピタゴラスの定理」と呼ばれるものがある。
a^2 + b^2 = c^2 を満たす正の整数の組 (a, b, c) のことを、ピタゴラス数と呼ぶ。
例えば、(3, 4, 5) や (5, 12, 13) などは有名なピタゴラス数である。

ピタゴラス数が無限個存在する
任意の原始的ピタゴラス数が (|m^2 ? n^2|, 2mn, m^2 + n^2) の形で表せることを示す。
https://nue2004.info/knowledge/knowledge97.htm

**デフォルトの名無しさん** · 2019/09/03(火) 09:27:31.81

＼　　　/　.::::::::::::::::::::::::;;:;;::,ｯ､:::::::::　　 )　く　数　す
　＼　l　 ,ｯｨrj,rｆ'"'"'"　　　 lﾐ:::::::　く　　れ　学　ま
　　　　 Y　　　　　　　　　　 ,!ﾐ:::::::　ヽ　　な　野　な
｀ヽ､　　|　　　　　　　　　　くミ::::::::　ﾉ　い　郎　い
　　　　 |､__　ｬー--＿ニゞ　｀i::::,rく　　　か　は
｀`''ｰ-　ゝ､'ｌ　￣ﾞ´彑,ヾ　　　}::;! ,ﾍ.）　　！　帰
　　　　　ﾞｿ　　　""""´｀　　　　　〉 L_　　　っ
　　　　　 /　　　　　　　　　　i　　,　　/|　　　　て　　　　r
≡＝-　〈´　,,.._　　　　　　　 i　　't-'ﾞ　|　,へ　　　　　,r┘
,､yx=''"　｀ｰ{ﾞ　＿, -､　　　　;　　l　　　ﾚ'　　ヽr､⌒ヽ'
　　　　　　　ﾞ､`--─ﾞ　　　　　 /!　　　　　　　　 `､
　　_,,､-　　　ﾞ､ー''　　　　／　;　　　　　　　　　　 `､
-''"_,,､-''"　　　ﾞ､　　　　／;;'　,'　　/　　　　　　　　、＼
-''"　　　／　　　`ｰ─''ぐ;;;;' ,'　　ノ　　　　　　
　　／／　　　 /　　　　　ヾ_､=ﾆﾞ

**デフォルトの名無しさん** · 2019/09/03(火) 13:20:54.78

どう考えてもスレチだよなぁ
必要なのはプログラムじゃなく紙と鉛筆っぽいし

**デフォルトの名無しさん** · 2019/09/03(火) 13:43:33.95

このスレは数学嫌いな奴多いなぁ
べつにちょっとぐらいいいじゃないか

**デフォルトの名無しさん** · 2019/09/03(火) 13:52:03.24

むしろこのスレは本当にコンピューター使わないと解けないような
パズル問題とかの方が解答つかないことが多い

**デフォルトの名無しさん** · 2019/09/03(火) 14:53:42.89

掛け算があるので加速的に左の解が増えるので追い付かなくなる予感。

**デフォルトの名無しさん** · 2019/09/03(火) 15:14:05.99

>>272
https://ideone.com/NIuUAj
C++。コードが正しければ解ナシ。

**デフォルトの名無しさん** · 2019/09/03(火) 15:15:29.58

(a^2 - b^2)^x + (2ab)^y=0
(a^2 + b^2)^z=0

の連立方程式解くとよさそうに見えるが。
解くのむずくて俺は無理。

**デフォルトの名無しさん** · 2019/09/03(火) 15:28:15.62

>>285
何かの冗談？それじゃ明らかに解無しなんですが

**デフォルトの名無しさん** · 2019/09/03(火) 15:31:15.82

>>257 Ruby
N = 10
X = Random.new.bytes(N)
puts X.unpack('C*').map{|c| '%02X' % c}.join(' '), X.unpack('B*')

結果
82 30 D4 E1 07 32 27 3E A2 E5
10000010001100001101010011100001000001110011001000100111001111101010001011100101

**デフォルトの名無しさん** · 2019/09/03(火) 15:38:54.45

自分で移項して解こうと思ったがキャパ超えててギブアップ。

>>286
解があることは証明されているのですか？数学ダメなんだよ。

**デフォルトの名無しさん** · 2019/09/03(火) 15:40:16.69

>>288
(a^2 + b^2)^z=0 <=> a = 0 and b = 0
a > b はどこ行ったの？
てか勝手に両辺＝０にしちゃその時点で必要性満たしてないよね

**デフォルトの名無しさん** · 2019/09/03(火) 15:45:42.09

数学ダメなのでセオリー知らないんだけど。マジ解らん。

正直すまんかった。

**デフォルトの名無しさん** · 2019/09/03(火) 15:47:50.03

あと、ちょっとだけ。
>>289
俺はaとbをゼロには規定してないよ。

**デフォルトの名無しさん** · 2019/09/03(火) 15:50:06.71

>>284
18行目の不等号逆じゃない？
x=y=z=2の時に出力出るはずだけど。

(元のお題ではxは3以上)

**デフォルトの名無しさん** · 2019/09/03(火) 15:52:04.84

>>292
https://ideone.com/ZNkEYb
弄ってみた。

**デフォルトの名無しさん** · 2019/09/03(火) 15:56:44.07

doubleの演算誤差出てるなｗｗｗｗ

**デフォルトの名無しさん** · 2019/09/03(火) 15:57:29.86

>>293　直しました。
大きな数で発見できているかな？

**デフォルトの名無しさん** · 2019/09/03(火) 16:00:10.37

いや、精度飛んでて、うまく測れてないな。

**デフォルトの名無しさん** · 2019/09/03(火) 16:01:59.48

演算誤差ではないか　誤差で=になるレベルじゃない
AとB出力してみ？

**デフォルトの名無しさん** · 2019/09/03(火) 16:02:55.16

多倍長無いと証明には至らないな。
というわけで今回は抜けるわ。
乱文申し訳ない。

**デフォルトの名無しさん** · 2019/09/03(火) 16:03:35.69

あ、doubleからstd::size_tになってたｗ

**デフォルトの名無しさん** · 2019/09/03(火) 16:10:08.37

色々弄ってみたけど、これで凍結しておくわ。
すまんかった。

**デフォルトの名無しさん** · 2019/09/03(火) 16:42:54.68

>>291
規程してないよって言ってるけど
貴方が提示した条件は a=0 and b=0 と同値ですよって指摘してるんですけど難しいですか私が言ってる事

**デフォルトの名無しさん** · 2019/09/03(火) 16:46:54.03

>>301
正直言えば難しいね。手を出さなければよかったとちょっと思ってる。
すまんな。

**デフォルトの名無しさん** · 2019/09/03(火) 21:38:14.04

>>277
なんでxだけ3以上なの？
yとzは本当に1以上の整数として解いていいの？
aとbは定数として扱うの？
なんなの？

**デフォルトの名無しさん** · 2019/09/03(火) 22:12:17.83

x=y=z=2以外の解があるか?

すべて自然数、変数　a>b、 (a^2 - b^2)^x + (2ab)^y = (a^2 + b^2)^z　の解

答えしらず。 a=2 b=1だけはいまのところ他にないを証明可能

**デフォルトの名無しさん** · 2019/09/03(火) 22:33:37.84

>>257
VB
https://paiza.io/projects/grWlkqU1Rb-dk-QNh69rRQ

**デフォルトの名無しさん** · 2019/09/03(火) 22:40:59.77

>>304
だからxだけ3以上でyとzは1以上の整数として計算していいか聞いてんだけど？
で、もしそうだったとしてなんでxだけ3以上に仮定してんのかも合わせて聞いてんだけど答えろよ

**デフォルトの名無しさん** · 2019/09/04(水) 00:41:31.51

304は3以上を仮定してない、すべて自然数

**デフォルトの名無しさん** · 2019/09/04(水) 02:57:47.93

あーこりゃ致命的に頭悪い奴か
数学も日本語も通じないとは

**デフォルトの名無しさん** · 2019/09/04(水) 07:57:08.75

定理を発見したら著作権で保護されるのかな。

**デフォルトの名無しさん** · 2019/09/04(水) 08:46:01.17

日本数学会に提出する前に
大学の教授にみてもらわないと

**デフォルトの名無しさん** · 2019/09/04(水) 09:59:12.24

次スレは数学禁止ってスレタイに入れないとな

**デフォルトの名無しさん** · 2019/09/04(水) 10:54:57.98

>>310
そして手柄を横取りされる定期

**デフォルトの名無しさん** · 2019/09/04(水) 11:24:41.75

お題: 平面上にいくつかの円 (内部も含む円) がある
それが重なったり重ならなかったりしていて、最も重なっている箇所ではN個の円が重なっているとする
このとき、各円の座標と半径が与えられた場合にNを返すプログラムを書け

**デフォルトの名無しさん** · 2019/09/04(水) 13:52:37.01

半年くらい前にそのお題あったが思いつかなかったんだよなー…モンテカルロなら作れるがｗ

https://mevius.5ch.net/test/read.cgi/tech/1549160513/405

**デフォルトの名無しさん** · 2019/09/04(水) 14:06:48.93

それ円周率パイとネイピア数のe の積が
N個の円の重なる唯一の x座標とy座標の円達を与えられて返すの辛くないか？

**デフォルトの名無しさん** · 2019/09/04(水) 14:13:24.75

>>315
辛くねえよ
どうやったら方程式解いて超越数が出てくんだよ
ちょっとは考えてからレスしろ

**デフォルトの名無しさん** · 2019/09/04(水) 14:29:48.47

例として313が N=4 で、それを与える円4つが
(x-ePi-1)^2+(y-ePi)^2=1
(x-ePi+1)^2+(y-ePi)^2=1
(x-ePi )^2+(y-ePi-1)^2=1
(x-ePi )^2+(y-ePi+1)^2=1
だったら大変かもしれない？

**デフォルトの名無しさん** · 2019/09/04(水) 17:19:01.11

>>273
これ解無しって言ってるけど自明じゃないよね
ホントにあってんのか？

**デフォルトの名無しさん** · 2019/09/04(水) 18:34:12.43

>>306
横レスだが
騒ぐ前に元の>>272の問題文を良く見なさい
それで自分で判断できなければ数学的な問題に取り組むのは止めておいたほうが良い

**デフォルトの名無しさん** · 2019/09/04(水) 18:42:19.25

>>319
一連のやり取り見て出題者がそこら辺理解してなさそうだったから改めて確認しただけなんですけど
>>272を見ただけでは>>306の全ての質問に答えられないことは明白なのに何いってんの？
数学の論理もわからねえくせに見当違いのお説教してんじゃねえよ

**デフォルトの名無しさん** · 2019/09/04(水) 18:49:05.83

5chはペアプレイではなくマルチプレイということをお忘れなく。

**デフォルトの名無しさん** · 2019/09/04(水) 19:10:06.78

>>318
省いててわかりずらいかもしれないがアウトライン。一般化はできないだろう解き方。

3^x + 4^y = 5^z　の自然数解は(2,2,2)唯一つ

mod 3で1 ≡ (-1)^z、　z偶数が必要
z=2wとおくと　3^x = (5^w + 2^y) (5^w - 2^y)
簡単な考察で右辺の後項が3の倍数ならば前項は3の倍数になりえないので後項=1、前項=3^xが必要
w偶数とすると結果2式をmod 3で比較して不成立、w奇数が必要
y>=3ならばmod 8で5 ≡ 3^x、任意のxで不成立
y=1ならば解なし

**デフォルトの名無しさん** · 2019/09/04(水) 19:23:20.13

かいてから考えたら間違ってるところがでてきた
ここまではいいとして、これあってないな

> y>=3ならばmod 8で5 ≡ 3^x、任意のxで不成立

**デフォルトの名無しさん** · 2019/09/04(水) 19:26:32.69

いやあってた
5^2 ≡　1 (mod 8)になってしまうとおもったら
w奇数だから、5^3 ≡　5 (mod 8)だった
5しかでない

**デフォルトの名無しさん** · 2019/09/04(水) 20:01:35.58

>>314
あら既出だったのか
Twitterで見つけてきたんだけど、その人もこのスレ見てたのかな
それとも問題自体が有名な問題なのかな？

**デフォルトの名無しさん** · 2019/09/04(水) 22:19:56.37

少なくとも自分はAOJで見た記憶がある
たしか高校生向けのコンテストの問題だったはず…

**デフォルトの名無しさん** · 2019/09/04(水) 22:31:18.96

>>313
座標と半径が与えられたら、ひたすらHypotするんだ！！
これ、ゲーム技術だから覚えておくとよいよ。（偉そう

**デフォルトの名無しさん** · 2019/09/04(水) 22:47:39.03

自作かとおもってたがWikipediaにほぼおなじのあった。解は指数2に限るという。
のってて解けてないとすると難問か

ピタゴラスの定理 - Wikipedia

Jesmanowicz 予想
1956年に Jesmanowicz が以下の予想を提出した。

(a, b, c) を原始ピタゴラス数、n を自然数とする。x, y, z が
(an)^x　+　(bn)^y　=　(cn)^z
で自然数解を持つには、x=y=z=2　であることが必要である。

**デフォルトの名無しさん** · 2019/09/04(水) 22:56:59.22

Jesmanowicz予想で検索

KAKEN　研究期間 2011 ? 2012　不定方程式におけるTerai予想とJesmanowicz予想

まず始めに、Terai予想のケース(1)のP=q=r=2の場合(Jesmanowicz予想)について考察した。
藤田育嗣氏(日本大学)との共同研究で、Jesmanowicz予想を三つ組みa,b,cがある合同条件を満たす場合に証明した。
Pingzhi Yuan氏(華南師範大学)との共同研究では、申請者の以前の研究結果を大幅に拡張することが出来た。
次に、Terai予想のケース(1)の一般的な場合について考察した。
最近、Florian Luca氏(メキシコ自治国立大学モレリア数学研究所)が、以前の研究の多くを(本質的に)一般化する結果を与えた。
その手法は、Baker理論とそのp進版の理論が有効に用いられていた。しかし、その結果は、不完全な点があり、申請者はその部分を補う計算を行なった。

さらに、申請者はTerai予想の類似問題を提起した。それは、
2以上の自然数p,q,rに対して、a^p+b^q=c^rを満たすa,b,cに対して、
指数型ディオファントス方程式c^x+b^y=a^zは、q=r=2かつc=b+1のときに限り自然数解x,y,zを持ち、
そのときにただ一つの自然数解(x,y,z)=(1,1,p)を持つである。
申請者は、Terai予想で扱われている三つ組みa,b,cについて考察を行い、
Baker理論とそのp進版の理論を用いて、いくつかの場合に予想は成立することを証明した。
特に、後半の主張である"解の一意性"を証明した。

最後に、Terai予想では扱われない三つ組みについても研究結果を得た。
まず、Alain Togbe氏(Purdue大学)との共同研究を行い、氏の以前の連続整数に関する研究を広く拡張することが出来た。
また、申請者は、三つ組みがある線形回帰数列の項として与えられる場合に方程式の解を決定した。
それによって寺井伸浩氏(足利工業大学)によって提起されたフィボナッチ数列に関する予想を解決した。
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-11J05674/

**デフォルトの名無しさん** · 2019/09/04(水) 23:07:59.22

完全解決してないが、結構解けてるらしい

早稲田大学整数論セミナーの予定 (2014年度第5回)

タイトル：原始ピタゴラス数に関する Jesmanowicz 予想について

アブストラクト： 1956 年, Jesmanowiczはピタゴラス数に関する指数型不定方程式
(m^2 - n^2)^x + (2mn)^y = (m^2 + n^2)^z 　は, ただ一つの正の整数解 (x; y; z) = (2; 2; 2) を持つことを予想した.
ただし, m > n, gcd(m; n) = 1, m ≠ n mod 2 を満たす正の整数とする.

Journal of Number Theory の論文 (2014 年) において, n = 2 とき Jesmanowicz 予想が成り立つことを証明した.
これは, 与えられた n > 1 に対し m について何も仮定せず Jesmanowicz 予想が成り立つ最初の結果である.
最先端の楕円曲線や modular formの理論から導かれる一般化された Fermat 方程式に関する結果を用いて, m に何も条件を付けずに Jesmanowicz 予想が成り立つことを証明することができた.

本講演では, これをさらに拡張して, n=2 が奇素数の冪でかつ m > 72n のときJesmanowicz予想が成り立つことを証明できたので紹介する.
これらの結果の系として, n=2 が 50 未満の奇数のとき Jesmanowicz 予想が成り立つことが容易に得られる.

https://www.waseda.jp/sem-wnt/kako/pdf2014/20140516.pdf

**デフォルトの名無しさん** · 2019/09/04(水) 23:25:42.22

>>313
VB
https://paiza.io/projects/JW7K9hSmkAVtXbO3II21Nw

**デフォルトの名無しさん** · 2019/09/05(木) 00:10:35.11

>>313
https://ideone.com/DdvszK
C++。暇だったので解いてみた。が、あってるかわからない。

**デフォルトの名無しさん** · 2019/09/05(木) 10:41:35.98

置く場所の最大サイズ２０００＊２０００くらいまでだとprocessingとかで半透明の円を重ね合わせれば一番濃いところが正解だから合ってるかどうかだいたい見て分かる
ｒが小数で半径が0.0001から１億くらいまでまちまちだと面倒

**デフォルトの名無しさん** · 2019/09/05(木) 10:53:13.59

>>327,331-332
俺とは問題の解釈が違うようだ？

**デフォルトの名無しさん** · 2019/09/05(木) 11:32:41.41

>>334
そいつらはいつものアホやからスルーしなはれ

**デフォルトの名無しさん** · 2019/09/05(木) 13:09:10.29

>>326
高校生レベル高いな
まぁアルゴリズムとか高校生でもすごい子いるもんなー
競プロとかすごいもんなー

**314** · 2019/09/05(木) 21:33:33.48

>>313 Java
https://paiza.io/projects/iamhQLuhZskbvv3lCIrj5Q
なんか思いつけたので書いた
いつもはideoneやけど、画像出力もしたくなったのでpaiza

入力データは https://mevius.5ch.net/test/read.cgi/tech/1549160513/405

**デフォルトの名無しさん** · 2019/09/06(金) 18:11:06.63

>>337
お前いつもスマートだよな

**デフォルトの名無しさん** · 2019/09/06(金) 21:58:05.28

材料グループAと材料グループBがあるとする。
それぞれには、ランダムな固有値を持っており、
固有値の差が、ある数値以下の組み合わせのみ使用可能とする。
ただし、材料グループA、B内の材料は一度使うとなくなるため一度しか組み合わせれない。
それぞれのグループの材料が100ずつあったとして適切に組み合わせれば
全てがマッチングできる。ただ人組でもペアを間違えるとマッチングできない。

こういったことを実現するためには、どういった考え方でプログラミングすればいいでしょうか。

**デフォルトの名無しさん** · 2019/09/06(金) 22:02:46.96

動的計画法でいいのかな？
オレできねーけど。

**デフォルトの名無しさん** · 2019/09/06(金) 22:06:24.07

>>339
各グループの材料を固有値の昇順にソートして小さい方からペア作ってくのではダメなのか？

**デフォルトの名無しさん** · 2019/09/06(金) 22:10:20.13

A:大<->小
B:小<->大

のペアがましといえばまし。
真ん中がマッチしない可能性はある。

**339** · 2019/09/06(金) 22:10:34.94

なるほど、とても簡単な問いだったのですね。
なんか難しい事ばかり考えていました。

**デフォルトの名無しさん** · 2019/09/06(金) 22:11:12.30

diff のアルゴリズムがもうちょっと複雑なのにも対応できるやつじゃなかったか？

**デフォルトの名無しさん** · 2019/09/06(金) 22:14:00.34

あー、差が以下か。
A:小<->大
B:小<->大

でいいわ。。。
俺もなんか難しいこと考えてた。そーりー。

**339** · 2019/09/06(金) 22:14:53.61

必ずマッチングできない100ずつあったとした場合でも昇順ソートして同じ順位にいるもので、比較してマッチングできれば実施、できなければ上位を参照してマッチングできたら抜けて、できなければさらに上位とマッチングみたいなことをすれば良いのか。

**339** · 2019/09/06(金) 22:23:16.91

あっ違う違う。
昇順にソートして組み合わせるとマッチングできないもの出てきます。
というのも差が最小の組み合わせではなくて、
差がある一定以下である事なので、昇順にソートして隣り合うものではダメです。

少し考えたのですが、全ての組み合わせを実施して、その計算結果、今回は差がある数値以下である数が多い組み合わせを採用するみたいなことになるんですかね

**デフォルトの名無しさん** · 2019/09/06(金) 22:44:43.03

>>347
適切な解が存在するケースで、小さい順の付き合わせでダメになる具体例を示せる？

**339** · 2019/09/06(金) 23:00:40.30

ないですね。
ということは、やはり最小のマッチング以外はありえないということになるのですね。

材料在庫が変動していたとしても、その瞬間の最小の差のペアを作ることが
一番効率の良いマッチング方法になるということか、、、。

**デフォルトの名無しさん** · 2019/09/06(金) 23:08:33.74

>>339
https://ideone.com/vjhJdO
C++。ちょっと思いついたのでコード書いてみたよ。
ちょっとグリードに組み合わせ作るようにしてみた。

**デフォルトの名無しさん** · 2019/09/06(金) 23:19:00.83

全てマッチングできるとは限らず最も多くマッチングできる組み合わせ
を求める　ならちょっと工夫必要そう

**デフォルトの名無しさん** · 2019/09/06(金) 23:24:40.52

皆さんありがとう。

最も多くマッチングさせるときは、閾値に一番近い選択を行うことがシンプルということかな？

>>350
コードありがとうございます。
プログラムを生業にしている者ではないのでC＋＋の開発環境から構築になりますが、試してみます。

**デフォルトの名無しさん** · 2019/09/06(金) 23:31:32.53

fix it.

**デフォルトの名無しさん** · 2019/09/06(金) 23:32:51.82

大したコードではないが、そこまで威力があるとは思わなかった。
動機なんてそんなもんか。

**蟻人間** ◆T6xkBnTXz7B0 · 2019/09/06(金) 23:43:04.03

お題: ある会社の営業曜日(複数可)と営業時間が与えられる。今月１ヶ月の営業時間の合計を求め、今月のカレンダーの下に表示せよ。ただし、その会社は祝日・祭日を特別扱いしないものとする。

**399** · 2019/09/07(土) 00:15:01.96

>>354
おぉ見るたびマッチング精度上がってる
ありがとうございます！
参考にさせてもらいます

**デフォルトの名無しさん** · 2019/09/07(土) 09:58:38.85

>>350
>>339は固有値の差と言ってるのに>>350は固有値の和でコード書いてるように見える