醜い番号UVA

Question

私はUVA問題から1500番目の醜い数を計算しようとしています。 136

（参考：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=72）

私のアルゴリズムは単純です：

• は、アレイ国連内のすべての醜い番号を追跡します。
• un [i]をi + 1の醜い数にします。

ステップ：

1. 番目醜い数のインデックスを保持するために、TMP変数CURを使用してください。

2. 計算未[CUR]×2、UN [CUR]×3と未[CUR]×5。

3. セットを使用して重複を排除し、未

4. ソート未[I + 1]は、常に可能な限り最小になることを保証するためにアレイにそれらを格納します。

5. cur変数を増やして、i + 1番目の醜い数のインデックスになります。

6. アレイ内に1500個の数字が生成されるまで繰り返す。

マイコード：

# include<iostream> 
# include<set> 
# include<algorithm> 

using namespace std; 

int main(void) { 
    long long un[1500] = { 0 }; 
    set<long long> us; 
    un[0] = 1; 
    us.insert(1); 
    int i = 1,unE = 0,cur = 0; 

    while(true) { 
     unE = 0; 
     sort(un,un+i); 
     if(us.find(un[cur]*2) == us.end()) { 
      un[i+unE] = un[cur]*2; 
      us.insert(un[i+unE]); 
      unE++; 
     } 
     if(i + unE > 1500 - 1) { 
      break; 
     } 
     if(us.find(un[cur]*3) == us.end()) { 
      un[i+unE] = un[cur]*3; 
      us.insert(un[i+unE]); 
      unE++; 
     } 
     if(i + unE > 1500 - 1) { 
      break; 
     } 
     if(us.find(un[cur]*5) == us.end()) { 
      un[i+unE] = un[cur]*5; 
      us.insert(un[i+unE]); 
      unE++; 
     } 
     i+=unE; 
     cur++; 
    } 
    sort(un,un+1500); 

    for(int i = 0; i < 1500; i++) { 
     cout << un[i] << " "; 
    } 
    cout << un[1500-1] << endl; 
} 

私のアルゴリズム出力せず、私が代わりに大きな数を取得しています859963392.で正しい番号、。誰かが正しい方向に私を指差してくれますか？

Answer 1

あなたのアルゴリズムは、ほぼ正しいです、しかしエラーがそのあなたべきではないのです1500番台の数字が生成されたときにトップになりますが、「curr」が1500番目の数字に達したときに表示されます。これは、 'curr'の後のすべての醜い数字が生成されているわけではないので、あなたはいつでも 'curr'の前にすべての醜い数字があることを確信しているだけです。あなたのアルゴリズムを最適化するためのもう一つの提案は、 'curr'の後のすべての数値に対してヒープを使うことです。毎回配列全体をソートする必要はなく、セットをまったく使う必要もありません。私のコードは以下の通りです：

#include<iostream> 
#include<queue> 
#include<vector> 
using namespace std; 
vector<long long> un; //using vector because we don't know how many ugly numbers we will need to generate 
//If we decide to use an array (the way you did) it is better to define it outside of main(). 
priority_queue<long long> nun; //priority queue used for storing the next ugly numbers 
const int TARGET=1500; //always good to store magical numbers as constants instead of having them appear all over the code 
int main() 
{ 
    un.push_back(1); //adding the first ugly number 
    for (int i=0;i<TARGET-1;++i) 
    /* 
    We have already found the first ugly number (1), 
    so we only need to find TARGET-1 more. 
    */ 
    { 
     nun.push(-un[i]*2); 
     nun.push(-un[i]*3); 
     nun.push(-un[i]*5); 
     //adding the next ugly numbers to the heap 
     /* 
     Adding them as negative numbers because priority_queue 
     keeps the largest number on the top and we need the smallest. 
     */ 
     while (-nun.top()==un[i]) 
     { 
      nun.pop(); 
      //removing duplicates 
      /* 
      We can prove that we will never have more than 3 copies 
      of a number in the heap and thus that this will not 
      affect the performance. 
      1) We will never have more than one copy of a number in un. 
      2) Each number can be added to nun in 3 different ways: 
      by multiplying a number form un by 2, 3 or 5. 
      */ 
     } 
     un.push_back(-nun.top()); 
     nun.pop(); 
     //adding the next ugly number to un 
    } 
    cout<<un[TARGET-1]<<endl; 
    /* 
    Indexing starts at 0 so the TARGETth number is at index TARGET-1. 
    */ 
    return 0; 
} 

私のプログラムは本当に859963392、正解を出力します。

編集：それについて少し考えた後、私は線形の複雑さにそれを持っています。コードは次のとおりです。

#include<iostream> 
#include<vector> 
//#include<conio.h> 
using namespace std; 
vector<long long> un; //using vector because we don't know how many ugly numbers we will need to generate 
//If we decide to use an array (the way you did) it is better to define it outside of main(). 
const int TARGET=1500; //always good to store magical numbers as constants instead of having them appear all over the code 
int l2=0,l3=0,l5=0; //store the indexes of the last numbers multiplied by 2, 3 and 5 respectively 
int main() 
{ 
    un.push_back(1); //adding the first ugly number 
    for (int i=0;i<TARGET-1;++i) 
    /* 
    We have already found the first ugly number (1), 
    so we only need to find TARGET-1 more. 
    */ 
    { 
     un.push_back(min(min(un[l2]*2,un[l3]*3),un[l5]*5)); 
     //adding the next ugly number to un 
     if (un[i+1]==un[l2]*2) //checks if 2 multiplied by the number at index l2 has been included in un, if so, increment l2 
     { 
      ++l2; 
     } 
     if (un[i+1]==un[l3]*3) //checks if 3 multiplied by the number at index l3 has been included in un, if so, increment l3 
     { 
      ++l3; 
     } 
     if (un[i+1]==un[l5]*5) //checks if 5 multiplied by the number at index l5 has been included in un, if so, increment l5 
     { 
      ++l5; 
     } 
     /* 
     Basically only one of the variables l2, l3 and l5 (the one we used) will be incremented in a cycle unless we can get a number 
     in more than one way, in which case incrementing more than one of them is how we avoid duplicates. 
     Uncomment the commented code to observe this. 
     P.S. @PaulMcKenzie I can deal without a debugger just fine. 
     */ 
     //cerr<<i<<": "<<l2<<"("<<un[l2]*2<<") "<<l3<<"("<<un[l3]*3<<") "<<l5<<"("<<un[l5]*5<<") "<<un[i+1]<<endl; 
     //getch(); 
    } 
    cout<<un[TARGET-1]<<endl; 
    /* 
    Indexing starts at 0 so the TARGETth number is at index TARGET-1. 
    */ 
    return 0; 
} 

EDIT2：最初の解決方法では、前の数字を使用しないため、ベクターもまったく必要ありません。したがって、変数を1つ使用することで、メモリごとに最適化することができます。ここでは、そのような実装である：

私たちは保存する必要がないことを考えると、最初の1に比べてあらゆる方法で（最後のものが悪化し、より良い（またはではありません）2つの競合ソリューションを持っているという結論に

#include<iostream> 
#include<queue> 
#include<vector> 
using namespace std; 
long long un; //last ugly number found 
priority_queue<long long> nun; //priority queue used for storing the next ugly numbers 
const int TARGET=1500; //always good to store magical numbers as constants instead of having them appear all over the code 
int main() 
{ 
    un=1; //adding the first ugly number 
    for (int i=0;i<TARGET-1;++i) 
    /* 
    We have already found the first ugly number (1), 
    so we only need to find TARGET-1 more. 
    */ 
    { 
     nun.push(-un*2); 
     nun.push(-un*3); 
     nun.push(-un*5); 
     //adding the next ugly numbers to the heap 
     /* 
     Adding them as negative numbers because priority_queue 
     keeps the largest number on the top and we need the smallest. 
     */ 
     while (-nun.top()==un) 
     { 
      nun.pop(); 
      //removing duplicates 
      /* 
      We can prove that we will never have more than 3 copies 
      of a number in the heap and thus that this will not 
      affect the performance. 
      1) We will never have more than one copy of a number in un. 
      2) Each number can be added to nun in 3 different ways: 
      by multiplying a number form un by 2, 3 or 5. 
      */ 
     } 
     un=-nun.top(); 
     nun.pop(); 
     //adding the next ugly number to un 
    } 
    cout<<un<<endl; 
    /* 
    Indexing starts at 0 so the TARGETth number is at index TARGET-1. 
    */ 
    return 0; 
} 

数字）。それらのうちの1つは、線形の時間の複雑さと線形のメモリの複雑さを持っています（しかし、それはNではありませんが、最適化されたソリューションは、もはや必要ではない数に使用されるメモリを解放します。したがって、Nが無限に近づくにつれて、メモリの複雑さはNに近づく）、もう1つはNlogNの時間の複雑さと、私たちが決定する必要があるメモリの複雑さがあります。ヒープに3つの数字を追加し、1から3の間のどこかに出るたびに（ヒープ内の数字は最大3回で、コピーのうちの1つをすでに取り出しているので、他の2つのコピーを取り除くことができます） 。したがって、そのメモリの複雑さは、定数と2Nの間のどこかにある可能性があります。私はさらなる分析を行った後でこの答えを編集するだろうが、私の最初の印象は、大きなNsの場合、メモリの複雑さはNよりも小さいということである。

さらに結論としては、線形解法はスピードワイドであり、NlogN解法は、しかし、それはまだ確認されていません。

EDIT3：NlogNソリューションは明らかにメモリワイズです。 Nが大きくなればなるほど、2,3,4,5で割り切れて、ほぼすべての数字が3で割り切れます。そのため、ほぼすべてのサイクルで、ヒープから3つの数値を取り除くため、それは成長しません。 Nが無限に近づくにつれて、メモリの複雑さは一定に近づきます。優先度キューのサイズをサイクルごとに、または最後に出力することで、これをテストできます。たとえば、N = 5000の場合、ヒープのサイズは1477です。しかし、Nが10000に達すると、サイズは2364にすぎません。

このソリューションは良いと思われますが、私は実際に元の分析で間違いを犯しました。ますます遅れていくことはありません。私が大きなNについて説明したように、すべての数は3つの2,3,5で割り切れます。そのため、ほぼ毎回増加し、保存する必要のある数字の数はほぼ一定に留まります。例えば、N = 5000の場合、l5 = 4308であり、l5とNとの間の数だけを記憶する必要があるので、690の数を記憶する必要がある。 Nが10000に達すると、l5 = 8891となり、1107の数値を格納する必要があります。それはほぼ倍増しているので、定数に近づいていることは明らかではありませんが、より多くのテストを行うと、テストが遅くなっていることが明らかになります。

理論的には、両方のメモリの複雑さはほぼ同じ速度で減速するはずですが、ヒープのサイズを最初に大きくするとメモリが増えます。

結論（3回目の魅力）は、線形解法がスピードワイズとメモリワイズの両方で優れています（ダイナミックメモリ割り当てが私のソリューションに実装されている場合はそうではありません。

Answer 2

より多くのコードにシンプルですが解決策isを読むことが難しい：

記録
、ブルートフォースソリューション、ちょうど彼らが醜いしているかどうかのためにすべての数字をチェックし、醜いのカウントを維持するための

#include <iostream> 

using namespace std; 

int main(){ 
    const int n = 1499; 
    int a [ 1500 ]; 
    int p1(0), p2(0), p3(0), end(0); 
    a [ 0 ] = 1; 
    while (end < n){ 
     while (a [ p1 ] * 2 <= a [ end ]) ++ p1; 
     while (a [ p2 ] * 3 <= a [ end ]) ++ p2; 
     while (a [ p3 ] * 5 <= a [ end ]) ++ p3; 
     if (a [ p1 ] * 2 < a [ p2 ] * 3 && a [ p1 ] * 2 < a [ p3 ] * 5) 
      a [ ++ end ] = a [ p1 ++ ] * 2; 
     else if (a [ p2 ] * 3 < a [ p3 ] * 5) 
        a [ ++ end ] = a [ p2 ++ ] * 3; 
       else a [ ++ end ] = a [ p3 ++ ] * 5; 
    } 
    cout << "The 1500'th ugly number is " << a [ end ] << ".\n"; 
    return 0; 
} 

ものは次のコードで自分のコンピュータ上で20秒以上を取る：

//uva136 preparer 
#include <iostream> 

using namespace std; 

typedef long long ll; 



bool is_ugly(int in) 
{ 

    while(true) 
    { 
     if(in % 5 ==0) 
      in /= 5; 
     else if(in %2==0) 
      in /=2 ; 
     else if (in % 3 == 0) 
      in/=3; 
     else 
      break; 

    } 
    if(in==1) 
     return true ; 
    else 
     return false ; 

} 

int main() 
{ 
    int c=0 ; 
    ll j=6; 
    int i=6; 
    for(j =6;(i<1501) ; j++) 
    { 
     if(isugly(j)) 
      i++; 
    } 
    cout<<j-1<<endl<<double(clock())/CLOCKS_PER_SEC;// because at the last iteration of four , j is updated to j+1 and we should minus it by one to make it no count . 
    return 0; 
}