2017-12-31 44 views
0

質問: 醜い番号は、唯一の素因数がシーケンス1、2、3、4、5、6、8、9、10、12 2、3または5である数であります15、...は最初の11の醜い数字を示しています。慣例により、1が含まれています。醜い番号 - DPアプローチ

数字nが与えられた場合、タスクはn’th醜い番号を見つけることです。 (https://www.geeksforgeeks.org/ugly-numbers/

回答:上記のリンクでの動的プログラミングアプローチ

擬似コード:

1 Declare an array for ugly numbers: ugly[n] 
2 Initialize first ugly no: ugly[0] = 1 
3 Initialize three array index variables i2, i3, i5 to point to 
    1st element of the ugly array: 
     i2 = i3 = i5 =0; 
4 Initialize 3 choices for the next ugly no: 
     next_mulitple_of_2 = ugly[i2]*2; 
     next_mulitple_of_3 = ugly[i3]*3 
     next_mulitple_of_5 = ugly[i5]*5; 
5 Now go in a loop to fill all ugly numbers till 150: 
For (i = 1; i < 150; i++) 
{ 
    /* These small steps are not optimized for good 
     readability. Will optimize them in C program */ 
    next_ugly_no = Min(next_mulitple_of_2, 
         next_mulitple_of_3, 
         next_mulitple_of_5); 

    ugly[i] = next_ugly_no  

    if (next_ugly_no == next_mulitple_of_2) 
    {    
     i2 = i2 + 1;   
     next_mulitple_of_2 = ugly[i2]*2; 
    } 
    if (next_ugly_no == next_mulitple_of_3) 
    {    
     i3 = i3 + 1;   
     next_mulitple_of_3 = ugly[i3]*3; 
    }    
    if (next_ugly_no == next_mulitple_of_5) 
    {  
     i5 = i5 + 1;   
     next_mulitple_of_5 = ugly[i5]*5; 
    } 

}/* end of for loop */ 
6.return next_ugly_no 

疑問:

私はDPのアプローチを理解していませんこの場合。

  1. サブ問題は何ですか?
  2. この場合の再帰とは何ですか?
  3. サブ問題はどのように重なっていますか?
  4. なぜ私たちは現在の醜い番号を追跡するのですか?なぜ2,3,5の倍数を通過するのではなく、各点を最小限にとどめてください。

    2,3,5と同様です。次に、それぞれの倍数をインクリメントする4,3,5、そして4,6,5 ...キーを押します。

関連質問:nth ugly number(。私は答えてweentが、私は、私が言及した上記の質問で混乱していた)

+1

ここにその記事の質問を投稿する必要があります。そのリンクが死んでしまうと、この全体の質問と答えは誰にとっても役に立たなくなってしまいます。 – Rob

+0

@Robが含まれています、ありがとうございます。答えも含まれています。まだ何か問題がある場合は教えてください。 –

答えて

2
  1. 部分問題:3の2の倍数であるすべての数字を、見つける、の5
  2. 再帰:過去の醜い数字を使用して将来の醜い数字を計算する。ダイナミックプログラミングソリューションは、ストレージの使用による再帰の必要性を短絡させます。
  3. オーバーラップ:出力は数値順である必要がありますので、どのサブ問題が次の順序で次のものを生成するかは不明です。
  4. なぜトラックを保持:スペースの削減が醜い配列を剪定することによって達成することができます。前の醜い番号を再利用することなく、あなただけの指数は2^nは、3^nは、5^nは

さらなる最適化を結果になるだろう再び必要ではないので、<分(i2、i3、i5)の値をすべて解除します。

+0

ポイント4を説明することができます。 –

+0

順序をつけた順序でトラックを保存するための2つのオプションがあります - 未来のトラックまたは過去のトラック。投稿されたソリューションは過去のものを追跡します。あなたのポイントに、発見されたそれぞれの醜い数字の3つの将来の醜い数字を計算することができました。しかし、将来の数字を保存し、重複を取り除く必要があります。この場合の将来のストレージは、過去のストレージよりも複雑に見えます。 – xeo

+0

https:// ideone。com/q3fmaは、N番目の数字のおおよその範囲を見積もり、すべての方法を計算することができないため、現在のところ最も優れた理想的なソリューションです。 – xeo