- ベストアンサー
部分和問題がわかりません。
部分和問題がわかりません。 [問題] n個の整数が配列Aに格納されていて、整数xの値を与えたときに、 A[i] + A[j] = x となるi,jが存在するかどうかを判定する、なるべく効率のよいアルゴリズムを示せ。 この問題は部分和問題のため、NP完全問題なので、総当たりのO(n^2)より効率のいい方法がないと思うのですが、もっと効率のよい方法が存在するのでしょうか？
- akisute3
- お礼率27% (30/108)
- その他（プログラミング・開発）
- 回答数5
- ありがとう数1
- みんなの回答 （5）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (4)
- beefisdead
- ベストアンサー率63% (92/145)
- Tacosan
- ベストアンサー率23% (3656/15482)
- bug_bug
- ベストアンサー率78% (36/46)
- beefisdead
- ベストアンサー率63% (92/145)
関連するQ&A
- 高校数学 整数問題
nは2以上の自然数とする。 (1) n個の自然数 x(1),x(2),…,x(n)のどれもnで割り切れないとき、 x(j)-x(i) (1≦i<j≦n) がnの倍数となる2つの自然数i,jが存在することを示せ。 (2) n個の自然数 a(1),a(2),…,a(n)からなる集合をSとする。Sの空でない部分集合で、その要素の和がnで割り切れるものが存在することを示せ。 (2)について、 (ア)a(1),a(2),…a(n)のうち少なくとも1つnで割り切れるものが存在する場合 と、 (イ)a(1),a(2)…a(n)がすべてnで割り切れない場合 に分けて、(イ)で(1)を利用すると思うのですが、どのように(1)を使えばよいのでしょうか？
- ベストアンサー
- 数学・算数
- m個の数字をn個のグループに分けるとき、
m個の数字をn個のグループに分けるとき、 各グループの和s(i) ,(1<=i<=n) が、指定した比 r(0):r(1): ・・・ :r(n-1):r(n) ( = s(0):s(1): ・・・ :s(n-1):s(n) ) に一番近くなるようなグループ分けを導けるアルゴリズムはありますか。 例えば、{1, 3, 4, 6}を和の比が1:2に一番近くなるように2つのグループに分けると、 {1, 4}, {3, 6} となります。(もし違ってたら指摘してください) アルゴリズムでなくても、こうしたら良いんじゃないか、という考えがありましたら 教えてください。 総当たりで調べる場合はどのようにすれば、効率良く調べられるかという点もお願いします。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 和の集まりを一括して，ひとつの数式で表示する表現方
X(i)とY(j)を正の整数とします．次の和の集まり X(i)＋Y(j) があるとします. X(i)＋Y(j), i＝1,2,...,p. （pは正の整数） j＝1,2,...,q. （qは正の整数） このとき，W(i,j)を W(i,j)＝X(i)＋Y(j)， i＝1,2,...,p， j＝1,2,...,q， と書いたとすれば，W(i,j)は，pq個あるすべての和：X(i)＋Y(j)を表している事になりますか？ この場合，曖昧な点や，瑕疵はありませんか？ また，上記の和 X(i)＋Y(j)，すなわち， X(1)＋Y(1)，X(1)＋Y(2)，・・・，X(1)＋Y(q)， X(2)＋Y(1)，X(2)＋Y(2)，・・・，X(2)＋Y(q)， ・・・・・・・・・・， X(p)＋Y(1)，X(p)＋Y(2)，・・・，X(p)＋Y(q)， を，一括して表現する既存の数学分野での数学的な表示方法は存在しますか？ 存在するとすれば，名称は何ですか？ 以上，教えて下さい．よろしくお願いします．
- ベストアンサー
- 数学・算数
- 因数分解と部分分数の和に関する問題
因数分解と部分分数の和に関する問題 f(x)=x^5-3x^4+5x^3-5x^2+3x-1の時、(1)因数分解せよ (2)(x^3-3x+3)/f(x)を部分分数の和に分解せよ。という問題です。(1)については、f(1)=0より、f(x)=(x-1)(x^4-2x^3+3x^2-2x+1)に因数分解できるのですが、さらに因数分解できるのでしょうか？ (2)については、部分分数の和に分解するポイントはどうすれば良いのでしょうか？すみませんが、よろしくお願いします。
- ベストアンサー
- 数学・算数
- 数Ｉで全然解けない問題が２つあって困ってます 助けて^^;
全然解けない問題があって困ってます^^; １つ目は・・。 和が６である２つの数があり、それらの平方の和は３２である。この２数を求めよ。 で、答えには３＋√７、３－√７になっているのですが、 何度やっても３＋√１１、３－√１１になってしまいます^^; （教科書に解説がありませんorz） 解と係数の関係を使って頑張って色々解いたのですが・・ ２つ目は・・。 不等式４－ｘ≦３ｘ≦２ｘ＋a を満たす整数ｘがちょうど３つ存在するような定数aの値の範囲を求めよ。 という問題で、こちらは解き方すら全く分かりませんorz どなたか教えてくださいおねがいしますorz
- ベストアンサー
- 数学・算数
- 数列の和の問題です。
以下の２問にお答え願いますでしょうか？ かなり時間かけたんですが解答がないんで困ってます。ご協力お願いいたします。 自然数ｘに対して√ｘの整数部分をｆ（ｘ）で表す。 (1)ｋを自然数とするとき、ｆ（ｘ）＝ｋを満たす自然数ｘの個数をｋを用い て表せ。 (2)ｎを自然数とするとき、次のｎ＾２個の整数 ｆ（１），ｆ（２），ｆ（３），・・・・・・，ｆ（ｎ＾２）の和をｎを 用いて表せ。
- 締切済み
- 数学・算数
- 等差数列の和を利用・・？
こんにちは。確率（情報量）の問題で分からないものがあるのでお願いします。 問. n個の事象Ｅ(i)【i=1～n】の生起確率をP(i)とするとき、 P(1)=a% P(i)=P(i-1)+1% とする。このとき生起確率の和が100%になるためには、最小の整数aとそのときのnをいくらにすればよいか。 【（）内の文字、数字は小文字です】 私は、この問題を解くときに、 P1=a P2=a+1 P3=a+2 ・ ・ の関係から、等差数列を使うのかなと思い、初項a公差1で S(n)={n^2+(2a-1)n}/2 これが100％になるときなので、{n^2+(2a-1)n}/2＝100という式を立てたのですが、 ここから最小の整数aとその時のnをどう求めていいか分りません。 そもそも数列を使用するべき問題なのかの自信もありません； どなたかご指導お願いいたします。
- ベストアンサー
- 数学・算数
