和を構成する複数の数値を求める式は

質問

会社で大変困っているのでお教えいただけたら幸いです。
以前にも同じ問いがあったかもしれませんが、例えば１から２０までの数字があってその中の数字をいくつ組み合わせてもいいので答えを１８にしたいのですが、その場合のエクセルでの関数や構文を教えていただけないでしょうか。大変困っています。
どうぞよろしくお願いします。

回答No.3

noname#52504 · ベストアンサー

[Visual Basic]カテゴリーでのご質問ということは、
数式に限らずVBAを用いた解決でもよいということでしょうか？

とりあえず、[最大の数]が20程度であれば、下記のように
すべての組み合わせをじみ～に調べ上げてもなんとかなるようです。
（[最大の数]が30を超えたあたりでオーバーフローします）
'-----------------------↓　ココカラ　↓-----------------------
Sub Sample()
　Dim a() As Integer
　s = Val(InputBox("総和を入力してください"))
　n = Val(InputBox("最大数を入力してください"))　
　If n > s Then n = s
　ReDim a(n)
　r = 1　
　For i = 2 ^ n To 1 Step -1
　　k = 0
　　For j = n To 1 Step -1
　　　If ((i Mod (2 ^ j)) / (2 ^ (j - 1))) >= 1 Then
　　　　a(j) = j
　　　Else
　　　　a(j) = 0
　　　End If
　　　k = k + a(j)
　　　If k > s Then Exit For
　　Next j
　　If k = s Then
　　　c = 2
　　　r = r + 1
　　　For j = n To 1 Step -1
　　　　If a(j) <> 0 Then
　　　　　Cells(r, c) = a(j)
　　　　　c = c + 1
　　　　End If
　　　Next j
　　End If
　Next i　
　MsgBox "終了　" & r - 1 & "通り"
End Sub
'-----------------------↑　ココマデ　↑-----------------------
総和：18，最大数：20　と指定すると、
{18}から{6,5,4,2,1}まで、46通りの組み合わせが
アクティブシートに表示されます。

虱潰しではなくもう少しスマートに、ということであれば、
下記のようなアプローチが有効かもしれません。

【１～Ｎの整数から、重複を許さず、順序を考慮せず、
　いくつかの数を選んだとき、
　その和がＳとなるようなすべての組み合わせ】
をＦ(Ｓ,Ｎ)で表すとします。

まず、
Ｆ(Ｓ,Ｎ)の各要素それぞれについて、最大の数Ｍは、
・Ｎ以下。
・Ｓ以下。
・（√(１＋８Ｓ)－１）／２　以上。
　（∵１＋２＋３＋…＋Ｋ = (Ｋ＋１）Ｋ／２）
ということが言えます。すなわち、
max_Ｍ：Ｎ，Ｓのより小さい数
min_Ｍ：（√(１＋８Ｓ)－１）／２　を切り上げた数
としたとき　min_Ｍ≦Ｍ≦max_Ｍ

一方、
Ｆ(Ｓ,Ｎ)の各要素のうち、最大の数がＭとなる組み合わせは、
Ｆ(Ｓ－Ｍ，Ｍ－１)の各要素にＭを加えたものです。

したがって、
【Ｆ(Ｓ，Ｎ)を求める】という課題は、
【min_Ｍ≦Ｍ≦max_Ｍ　であるすべてのＭについて、Ｆ(Ｓ－Ｍ，Ｍ－１)を求める】
というという課題に帰結し、
０≦Ｓ－Ｍ＜Ｓ，０＜Ｍ－１＜Ｎ　ですから、
再帰的に処理すれば有限の回数で終了します。

例えばこんな感じ。
'------------------------------↓　ココカラ　↓------------------------------
Sub Sample2()
　Dim aryA As Variant
　Dim aryB As Variant　
　s = Val(InputBox("総和を入力してください"))
　n = Val(InputBox("最大数を入力してください"))
　aryA = SubP(s, n)　
　For i = 1 To UBound(aryA)
　　aryB = Split(aryA(i), ",")
　　For j = 0 To UBound(aryB)
　　　Cells(i + 1, j + 2) = aryB(j)
　　Next j
　Next i　
　MsgBox "終了　" & UBound(aryA) & "通り"
End Sub

Function SubP(ByVal s As Integer, ByVal n As Integer) As Variant
　Dim aryA As Variant
　Dim aryB As Variant　
　ReDim aryB(0)　
　If n > s Then
　　maxM = s
　Else
　　maxM = n
　End If
　minM = -Int(-((1 + 8 * s) ^ 0.5 - 1) / 2)
　For m = maxM To minM Step -1
　　b = UBound(aryB)
　　If m = s Then
　　　ReDim Preserve aryB(b + 1)
　　　aryB(b + 1) = m
　　Else
　　　aryA = SubP(s - m, m - 1)
　　　a = UBound(aryA)
　　　ReDim Preserve aryB(b + a)
　　　For i = 1 To a
　　　　aryB(b + i) = m & "," & aryA(i)
　　　Next i
　　End If
　Next m　
　SubP = aryB
End Function
'------------------------------↑　ココマデ　↑------------------------------

実際動かしてみるとわかりますが、こちらの方がかなり速いですね。
また、Ｆ(70,70)（29927通り)　ぐらいの規模でも一応機能します。
ただし、かなり珍妙な書き方をしているので、
コーディングは参考にしないほうが良いかも。

ワークシート関数でも、
配列処理を工夫すれば原理的には不可能ではないと思いますが、
そもそもExcelは再帰処理や反復処理には不向きですし、
すべて書き出してチェックするにしても、
Ｆ(18,18)の場合、単純計算で2^18≒26万通りですから、
あまり現実的ではありません。

以上ご参考まで。長乱文陳謝。

お礼

本当にありがとうございました。
エクセルが面白く思えてきました。
「無理かな」なんて思ってましたが、驚きです。
心から感謝申し上げます。

回答No.2

imogasi

＞関数や構文を教えていただけないでしょうか
エクセル関数などの問題ではありません。方法を教えてください。すぐ関数で書いて見せます、といっても言いすぎでは無いでしょう。
単純にエクセルの関数で表す課題ではないのです。
しかし、どう計算したら、無限の計算回数にならなくて済むか、これが分からないのです。
アルゴリズムといわれる、どのようににして計算回数を少なくて、解を求められるかそういう数学的な裏づけのあるやり方の発見が必要ですです。これが会があれば２０元の整係数不定方程式が解けることになりますが、そういう解法は聞いたことがありません。
私はいつも言っている。もし良い回答が出なければ、組み合わせなど数学に詳しい方の見るコーナーにでも質問したら。

補足

早速のアドバイスありがとうございます。
なかなかそのような発想になりませんでして、いろいろな文献や他のコーナーは見たのですが、理解が出来ず藁をもすがる思いでした。
ありがとうございました。

回答No.1

redfox63

で、何が分からないのでしょう？
丸投げではなく 疑問に思う点または不明な点を的を絞って質問しましょう
自分で考えた数式やコードがあるならそれらを投稿しましょう
# 一般公開が無理な部分は伏字にするなどして …

1から20までの数字は重複して使えるのでしょうか
重複してよいのであれば １が18個とかでもいいのですか

補足

早速にありがとうございます。
１から２０までの数字は重複して使用は出来ず、組み合わせのみ可能で、例えば１８には１と１７だけでなく１と２と１５など複数に足されていくことも想定したいと考えています。
今のところ力技ですが、２つを足した場合、３つを足した場合、４つを足した場合などと想定し、抽出画面と数字の入力シートをつくり、数字入力シートに１から２０までの整理番号を付したうえ、１から２０までの数字を入力します。抽出画面シートに３つを足して１８にする場合では、１行目を項目として
A2=IF(A2=0,0,IF(VLOOKUP(A2,数字の入力シート!$A$1:$B$20,3)=0,-1,VLOOKUP(A2,数字の入力シート!$A$1:$B$20,3)))
B2=IF(B2=0,0,IF(VLOOKUP(B2,数字の入力シート!$A$1:$B$20,3)=0,-1,VLOOKUP(B2,数字の入力シート!$A$1:$B$20,3)))
C2=IF(C2=0,0,IF(VLOOKUP(C2,数字の入力シート!$A$1:$B$20,3)=0,-1,VLOOKUP(C2,数字の入力シート!$A$1:$B$20,3)))
としてD列に合計欄を設けて
=IF(OR(A2<0,B2<0,C2<0),0,SUM(A2:C2))と入力し、
A.B.C.D行をそれぞれ列コピーしすべてを計算させたうえでオートフィルターをかけ、D列で答えが１８になるものを選んできました。
単純に全部をそれぞれに足し合わせてすべての答えから抽出する方法なのですが、２つの場合、４つの場合などと場合分けしたシートを作る必要が出たり、かなりデータ量が多くなってしまいました。
そこで、なにかいい方法がないかとお聞きした次第です。
説明不足で申し訳ありませんでした。