2^i * 5^j昇順でフォームの番号を印刷する方法を教えてください。
For eg:
1, 2, 4, 5, 8, 10, 16, 20
2269 次
10 に答える
2
これは実際には非常に興味深い質問です。特に、これを N^2 または NlogN の複雑さにしたくない場合はなおさらです。
私がすることは次のとおりです。
- 2 つの値 (i と j) と数式の結果を含むデータ構造を定義します。
- このデータ構造を含むコレクション (std::vector など) を定義します。
- 値 (0,0) でコレクションを初期化します (この場合、結果は 1 です)
- ループ内で次の操作を行います。
- コレクションを調べて、値が最小のインスタンスを取得します
- コレクションから削除します
- これを印刷する
- 処理したばかりのインスタンスに基づいて 2 つの新しいインスタンスを作成します
- 最初のインスタンスでは、i をインクリメントします
- 2 番目のインスタンスでは、j をインクリメントします
- 両方のインスタンスをコレクションに追加します (まだコレクションにない場合)
- 飽きるまでループ
適切なデータ構造とコレクションを選択することで、パフォーマンスを簡単に調整できます。たとえば、C++ では、キーが式の結果であり、値がペア (i,j) である std::map を使用できます。最小値を取得すると、マップ (*map.begin()) 内の最初のインスタンスが取得されます。
それを説明するために、私はすぐに次のアプリケーションを書きました (動作しますが、それ以上のコメントは含まれていません。申し訳ありません)。
#include <math.h>
#include <map>
#include <iostream>
typedef __int64 Integer;
typedef std::pair<Integer,Integer> MyPair;
typedef std::map<Integer,MyPair> MyMap;
Integer result(const MyPair &myPair)
{
return pow((double)2,(double)myPair.first) * pow((double)5,(double)myPair.second);
}
int main()
{
MyMap myMap;
MyPair firstValue(0,0);
myMap[result(firstValue)] = firstValue;
while (true)
{
auto it=myMap.begin();
if (it->first < 0) break; // overflow
MyPair myPair = it->second;
std::cout << it->first << "= 2^" << myPair.first << "*5^" << myPair.second << std::endl;
myMap.erase(it);
MyPair pair1 = myPair;
++pair1.first;
myMap[result(pair1)] = pair1;
MyPair pair2 = myPair;
++pair2.second;
myMap[result(pair2)] = pair2;
}
}
于 2011-09-27T16:30:06.557 に答える
2
O(N) ソリューションの場合、これまでに見つかった数値のリストと 2 つのインデックスを使用できます。1 つは次に 2 を掛ける数値を表し、もう 1 つは次に 5 を掛ける数値を表します。次に、各反復で小さい方を選択するための 2 つの候補値があります。
Python の場合:
numbers = [1]
next_2 = 0
next_5 = 0
for i in xrange(100):
mult_2 = numbers[next_2]*2
mult_5 = numbers[next_5]*5
if mult_2 < mult_5:
next = mult_2
next_2 += 1
else:
next = mult_5
next_5 += 1
# The comparison here is to avoid appending duplicates
if next > numbers[-1]:
numbers.append(next)
print numbers
于 2011-09-28T03:57:40.497 に答える
2
これは、関数型プログラミング スタイルに適しています。F# の場合:
let min (a,b)= if(a<b)then a else b;;
type stream (current, next)=
member this.current = current
member this.next():stream = next();;
let rec merge(a:stream,b:stream)=
if(a.current<b.current) then new stream(a.current, fun()->merge(a.next(),b))
else new stream(b.current, fun()->merge(a,b.next()));;
let rec Squares(start) = new stream(start,fun()->Squares(start*2));;
let rec AllPowers(start) = new stream(start,fun()->merge(Squares(start*2),AllPowers(start*5)));;
let Results = AllPowers(1);;
結果とうまく機能し、現在の値と次のメソッドを持つストリーム タイプになります。
それを歩く：
- 完全性のために min を定義します。
- 現在の値を持つストリーム型と、新しい文字列 (基本的には数値ストリームの先頭と末尾) を返すメソッドを定義します。
- 関数 merge を定義します。これは、2 つのストリームの現在の値のうち小さい方を取り、そのストリームをインクリメントします。その後、再帰的にストリームの残りを提供します。基本的に、順序どおりの 2 つのストリームが与えられると、順序どおりの新しいストリームが生成されます。
- 正方形を 2 の累乗で増加するストリームと定義します。
- AllPowers は開始値を取り、この 5 の累乗数ですべての正方形から得られるストリームをマージします。それを 5 倍して得られるストリームとマージします。これらは 2 つのオプションしかないためです。結果のツリーが効果的に残されます
その結果、ますます多くのストリームがマージされるため、次のストリームをマージします
1、2、4、8、16、32...
5、10、20、40、80、160...
25、50、100、200、400...
.
.
. これらすべてをマージすると、末尾再帰やコンパイラの最適化などでかなり効率的であることがわかります。
これらは、次のようにコンソールに出力できます。
let rec PrintAll(s:stream)=
if (s.current > 0) then
do System.Console.WriteLine(s.current)
PrintAll(s.next());;
PrintAll(Results);
let v = System.Console.ReadLine();
同様のことは、再帰と関数を値として渡すことができる言語で実行できます (関数を変数として渡すことができない場合は、もう少し複雑になります)。
于 2011-09-27T16:43:34.277 に答える
1
この問題を行列として視覚化しMますM(i,j) = 2^i * 5^j。これは、行と列の両方が増加していることを意味します。
entry から明確に始まるように、昇順でエントリに線を引くことを考えてみてください(1,1)。エントリにアクセスすると、行と列が増加する条件により、これらのセルによって形成される形状が常に整数のパーティション(英語表記) になります。このパーティションを追跡しmu = (m1, m2, m3, ...)ますmi( は行内の小さいエントリの数です。iしたがってm1 >= m2 >= ...)。次に、比較する必要がある唯一のエントリは、パーティションに追加できるエントリです。
これは大雑把な例です。xすべてのs ( ) にアクセスしたと仮定すると、smu = (5,3,3,1)のみを確認する必要があります。@
x x x x x @
x x x @
x x x
x @
@
したがって、チェックの数は、追加可能なセルの数です (ポセットの観点から考える場合は、ブルハット順序で上に行く方法の数と同じです)。
partitionmuを指定すると、追加可能な状態が何であるかを簡単に判断できます。0最後の正のエントリに続く s の無限の文字列をイメージします。次に、 の場合に限り、 を増やすことがmiでき1ますm(i-1) > mi。
例に戻ると、またはまたはまたはmu = (5,3,3,1)を増やすことができます。m1 (6,3,3,1)m2 (5,4,3,1)m4 (5,3,3,2)m5 (5,3,3,1,1)
次に、問題の解決策として、パーティションの正しいシーケンス (飽和チェーン) を見つけます。擬似コード:
mu = [1,0,0,...,0];
while (/* some terminate condition or go on forever */) {
minNext = 0;
nextCell = [];
// look through all addable cells
for (int i=0; i<mu.length; ++i) {
if (i==0 or mu[i-1]>mu[i]) {
// check for new minimum value
if (minNext == 0 or 2^i * 5^(mu[i]+1) < minNext) {
nextCell = i;
minNext = 2^i * 5^(mu[i]+1)
}
}
}
// print next largest entry and update mu
print(minNext);
mu[i]++;
}
これを Maple で書き、12 回の反復後に停止しました。
1, 2, 4, 5, 8, 10, 16, 20, 25, 32, 40, 50
出力されたセルのシーケンスが追加され、次のようになりました。
1 2 3 5 7 10
4 6 8 11
9 12
この行列表現に対応する:
1, 2, 4, 8, 16, 32...
5, 10, 20, 40, 80, 160...
25, 50, 100, 200, 400...
于 2011-10-10T22:47:56.723 に答える
1
2 つのループがあり、1 つはインクリメント、もう 1 つはインクリメントiで、jどちらもゼロから開始します。（質問のタイトルで乗算記号が紛らわしい）
非常に簡単なことを行うことができます：
- 配列内のすべての項目を追加
- 配列をソートする
または、より多くの数学分析を備えた他のソリューションが必要ですか?
編集：マージソート問題との類似性を活用することによるよりスマートなソリューション
2^iとの数の無限集合を 2 つの独立したストリーム/リストとして想像すると、この問題はよく知られているマージ ソート5^jの問題と非常によく似ています。
したがって、解決策の手順は次のとおりです。
- ストリーム (2 と 5) のそれぞれから 2 つの数字を 1 つ取得します。
- 比較
- 最小値を返す
- 以前に返された最小のストリームから次の番号を取得します
以上です！;)
PS: マージソートの複雑さalwaysはO(n*log(n))
于 2011-09-27T15:53:08.997 に答える
0
私に課された問題は、無限の解のセットを返すことでした。樹木の利用について考えてみましたが、i と j の値が無数にあるため、いつ伐採して剪定するかを判断するのに問題があると感じました。ふるいアルゴリズムを使用できることに気付きました。ゼロから始めて、各正の整数に i と j の値があるかどうかを判断します。これは、 answer = (2^i)*(2^j) を逆にして、代わりに i を解くことで容易になりました。これにより、i = log2 (answer/ (5^j)) が得られました。コードは次のとおりです。
class Program
{
static void Main(string[] args)
{
var startTime = DateTime.Now;
int potential = 0;
do
{
if (ExistsIandJ(potential))
Console.WriteLine("{0}", potential);
potential++;
} while (potential < 100000);
Console.WriteLine("Took {0} seconds", DateTime.Now.Subtract(startTime).TotalSeconds);
}
private static bool ExistsIandJ(int potential)
{
// potential = (2^i)*(5^j)
// 1 = (2^i)*(5^j)/potential
// 1/(2^1) = (5^j)/potential or (2^i) = potential / (5^j)
// i = log2 (potential / (5^j))
for (var j = 0; Math.Pow(5,j) <= potential; j++)
{
var i = Math.Log(potential / Math.Pow(5, j), 2);
if (i == Math.Truncate(i))
return true;
}
return false;
}
}
于 2015-07-30T01:30:34.020 に答える
0
数学者として、このようなものを見ていつも最初に考えるのは、「対数は役に立つのか?」ということです。
この場合はそうかもしれません。
シリーズ A が増加している場合、シリーズ log(A) も増加しています。A のすべての項は 2^i.5^j の形式であるため、級数 log(A) のすべての要素は i.log(2) + j.log(5) の形式になります。
次に、同様に増加しているシリーズ log(A)/log(2) を見ることができ、その要素は i+j.(log(5)/log(2)) の形式です。
この最後の系列 (これを B と呼びます) の完全な順序付きリストを生成する i と j を計算すると、その i と j は系列 A も正しく生成します。
これは問題の性質を変えているだけですが、うまくいけば解決しやすくなるでしょう。各ステップで、i を増やして j を減らしたり、その逆を行ったりできます。
できる初期の変更 (i,j の変換または単に transorms と呼ぶ場合があります) のいくつかを見ると、どこに向かっているのかの手がかりが得られます。
明らかに、i を 1 増やすと B が 1 増えます。ただし、log(5)/log(2) が約 2.3 であることを考えると、i を 2 減らしながら j を 1 増やすと、わずか 0.3 の増加になります。問題は、各段階で、i と j の変化に対する B の可能な最小の増加を見つけることです。
これを行うために、i と j の最も効率的な変換 (つまり、それぞれに何を足したり、何を引いたりするか) を増やして、シリーズの中で可能な限り最小限の増加を得るために、記録を残しました。次に、有効な方を適用します (つまり、i と j が負にならないようにします)。
各段階で i または j を減らすことができるため、個別にチェックできる 2 つのクラスの変換が効果的に存在します。新しい変換は、将来のチェックに含まれるのに最高の総合スコアを持っている必要はありません。そのクラスの他のどの変換よりも優れているだけです.
私の考えをテストするために、LinqPad で一種のプログラムを作成しました。注意すべき重要な点は、Dump() メソッドはオブジェクトを画面に出力するだけであり、構文/構造は実際の c# ファイルに対して有効ではないということです。ただし、実行したい場合に変換するのは簡単なはずです。
明示的に説明されていないことは、コードから理解できることを願っています。
void Main()
{
double C = Math.Log(5)/Math.Log(2);
int i = 0;
int j = 0;
int maxi = i;
int maxj = j;
List<int> outputList = new List<int>();
List<Transform> transforms = new List<Transform>();
outputList.Add(1);
while (outputList.Count<500)
{
Transform tr;
if (i==maxi)
{
//We haven't considered i this big before. Lets see if we can find an efficient transform by getting this many i and taking away some j.
maxi++;
tr = new Transform(maxi, (int)(-(maxi-maxi%C)/C), maxi%C);
AddIfWorthwhile(transforms, tr);
}
if (j==maxj)
{
//We haven't considered j this big before. Lets see if we can find an efficient transform by getting this many j and taking away some i.
maxj++;
tr = new Transform((int)(-(maxj*C)), maxj, (maxj*C)%1);
AddIfWorthwhile(transforms, tr);
}
//We have a set of transforms. We first find ones that are valid then order them by score and take the first (smallest) one.
Transform bestTransform = transforms.Where(x=>x.I>=-i && x.J >=-j).OrderBy(x=>x.Score).First();
//Apply transform
i+=bestTransform.I;
j+=bestTransform.J;
//output the next number in out list.
int value = GetValue(i,j);
//This line just gets it to stop when it overflows. I would have expected an exception but maybe LinqPad does magic with them?
if (value<0) break;
outputList.Add(value);
}
outputList.Dump();
}
public int GetValue(int i, int j)
{
return (int)(Math.Pow(2,i)*Math.Pow(5,j));
}
public void AddIfWorthwhile(List<Transform> list, Transform tr)
{
if (list.Where(x=>(x.Score<tr.Score && x.IncreaseI == tr.IncreaseI)).Count()==0)
{
list.Add(tr);
}
}
// Define other methods and classes here
public class Transform
{
public int I;
public int J;
public double Score;
public bool IncreaseI
{
get {return I>0;}
}
public Transform(int i, int j, double score)
{
I=i;
J=j;
Score=score;
}
}
私はこれの効率を気にしていませんが、他のいくつかのソリューションよりも優れていると強く思っています。なぜなら、各段階で行う必要があるのは、変換のセットをチェックすることだけです-「n」と比較してこれらの数を計算するだけです自明ではありません。先に進むほど変換が多くなるため、明らかに関連していますが、新しい変換の数は数が増えるとほとんどなくなるため、おそらく O(1) になります。このOのものはいつも私を混乱させました。;-)
他のソリューションに対する利点の 1 つは、積を計算しなくても i,j を計算できるため、実際の数値自体を計算しなくても数列を計算できることです。
最初の 230 個の数の後 (int がスペースを使い果たしたとき) の価値については、毎回 9 つの変換をチェックする必要がありました。そして、オーバーフローした唯一の合計を考えると、最初の 100 万件の結果について if を実行し、i=5191 と j=354 になりました。変換の数は 23 でした。リスト内のこの数のサイズは、約 10^1810 です。このレベルに到達するまでの実行時間は約 5 秒でした。
PSこの回答が気に入ったら、私はこれに何年も費やしたので、お気軽にお友達に教えてください。または、実際にコメントして、あなたの考えを教えてください。:)
于 2011-09-28T15:10:08.683 に答える
0
O(nlogn) で実行できる場合は、次の簡単な解決策があります。
Get an empty min-heap
Put 1 in the heap
while (you want to continue)
Get num from heap
print num
put num*2 and num*5 in the heap
そこにあります。最小ヒープとは、最小ヒープを意味します
于 2011-09-27T22:42:03.570 に答える
0
まず第一に、（他の人がすでに述べたように）この質問は非常に漠然としています!!!
それにもかかわらず、私はあなたのあいまいな方程式とあなたの期待される結果としてのパターンに基づいてショットを与えるつもりです. したがって、あなたがやろうとしていることに以下が当てはまるかどうかはわかりませんが、Java コレクションについてのアイデアが得られるかもしれません!
import java.util.List;
import java.util.ArrayList;
import java.util.SortedSet;
import java.util.TreeSet;
public class IncreasingNumbers {
private static List<Integer> findIncreasingNumbers(int maxIteration) {
SortedSet<Integer> numbers = new TreeSet<Integer>();
SortedSet<Integer> numbers2 = new TreeSet<Integer>();
for (int i=0;i < maxIteration;i++) {
int n1 = (int)Math.pow(2, i);
numbers.add(n1);
for (int j=0;j < maxIteration;j++) {
int n2 = (int)Math.pow(5, i);
numbers.add(n2);
for (Integer n: numbers) {
int n3 = n*n1;
numbers2.add(n3);
}
}
}
numbers.addAll(numbers2);
return new ArrayList<Integer>(numbers);
}
/**
* Based on the following fuzzy question @ StackOverflow
* http://stackoverflow.com/questions/7571934/printing-numbers-of-the-form-2i-5j-in-increasing-order
*
*
* Result:
* 1 2 4 5 8 10 16 20 25 32 40 64 80 100 125 128 200 256 400 625 1000 2000 10000
*/
public static void main(String[] args) {
List<Integer> numbers = findIncreasingNumbers(5);
for (Integer i: numbers) {
System.out.print(i + " ");
}
}
}
于 2011-09-27T16:35:43.757 に答える
0
誰もが今までに答えを持っていると確信していますが、この解決策の方向性を示したかっただけです..
http://www.careercup.com/question?id=16378662の Ctrl C + Ctrl V です 。
void print(int N)
{
int arr[N];
arr[0] = 1;
int i = 0, j = 0, k = 1;
int numJ, numI;
int num;
for(int count = 1; count < N; )
{
numI = arr[i] * 2;
numJ = arr[j] * 5;
if(numI < numJ)
{
num = numI;
i++;
}
else
{
num = numJ;
j++;
}
if(num > arr[k-1])
{
arr[k] = num;
k++;
count++;
}
}
for(int counter = 0; counter < N; counter++)
{
printf("%d ", arr[counter]);
}
}
于 2013-03-20T19:23:19.710 に答える