Anzahl der Möglichkeiten zu schreiben, die n als Summe von Potenzen von 2

Gibt es irgendeinen Algorithmus, um herauszufinden, wie viele Möglichkeiten gibt es für eine Zahl schreiben zum Beispiel n , mit der Summe der Leistung von 2 ?

Beispiel : für 4 gibt es vier Möglichkeiten :

4 = 4 
4 = 2 + 2 
4 = 1 + 1 + 1 + 1
4 = 2 + 1 + 1

Dank.

  • Wollen Sie differenzieren zwischen 4 = 2 + 1 + 1 und 4 = 1 + 1 + 2 oder sind diejenigen angesehen werden, da die gleichen?
  • Haben Sie gelöst 1, 2, 3, 4, 5, 6, 7 und sichtbar, wenn eine triviale Muster entsteht?
  • Danke, Nein, ich möchte nicht zwischen Ihnen zu unterscheiden. und ich sah ein Muster, wie fibo-Algorithmus, jedoch bin ich nicht sicher.
  • Ist es nicht einfach, eine Teilmenge-Summe-problem ? Oder sind Sie interessiert an einer geschlossenen Formel?
  • Ich denke, etwa eine Stunde, aber ich bin mir nicht sicher. eine Frage, die ich stellte.
  • Es gibt viel Informationen, einschließlich der Wiederholung Beziehungen für diese Sequenz an der Die On-Line Encyclopedia of Integer Sequences - A018819.

InformationsquelleAutor Hossein Mardani | 2012-11-20
  1. 3

    Angenommen, g(m) die Anzahl der Möglichkeiten, zu schreiben m als Summe von Potenzen von 2. Wir verwenden f(m,k) repräsentiert die Anzahl der Möglichkeiten zu schreiben m als Summe von Potenzen von 2 mit allen zahlen' Energie kleiner als oder gleich k ist. Dann können wir reduzieren die Gleichung:

    if m==0 f(m,k)=1;    
if k<0 f(m,k)=0;    
if k==0 f(m,k)=1;    
if m>=power(2,k) f(m,k)=f(m-power(2,k),k)+f(m,k-1);//we can use power(2,k) as one of the numbers or not.    
else f(m,k)=f(m,k-1);

    Take 6 als Beispiel:

    g(6)=f(6,2)
=f(2,2)+f(6,1)
=f(2,1)+f(4,1)+f(6,0)
=f(0,1)+f(2,0)+f(2,1)+f(4,0)+1
=1+1+f(0,1)+f(2,0)+1+1
=1+1+1+1+1+1
=6

    Hier ist der code, der unter:

    #include<iostream>
using namespace std;

int log2(int n)
{
    int ret = 0;
    while (n>>=1) 
    {
        ++ret;      
    }
    return ret;
}

int power(int x,int y)
{
    int ret=1,i=0;
    while(i<y)
    {
        ret*=x;
        i++;
    }
    return ret;
}

int getcount(int m,int k)
{
    if(m==0)return 1;
    if(k<0)return 0;
    if(k==0)return 1;
    if(m>=power(2,k))return getcount(m-power(2,k),k)+getcount(m,k-1);
    else return getcount(m,k-1);

}

int main()
{
    int m=0;
    while(cin>>m)
    {
        int k=log2(m);
        cout<<getcount(m,k)<<endl;
    }
    return 0;
}

    Hoffe, es hilft!

    • Sehr gut .... Thank u .
    InformationsquelleAutor Chasefornone
  2. 2

    Eine rekursive definition der Folge (aus Peter ' s link zu A018819):

    f(n) = 1 falls n = 0 Sum(j = 0..[n/2], f(j)), wenn n > 0 http://mathurl.com/nuaarfm.png

    InformationsquelleAutor cmbuckley
  3. 0

    Wollen Sie die Anzahl der Möglichkeiten, in denen Sie Ausdrücken können, eine Zahl als Summe der Leistung der 2.
    Erstens müssen Sie die Anzahl bits, die in dieser bestimmten Zahl, da die Anzahl der bit geben uns die Mindestanzahl erforderlich, um es auszudrücken, als die Summe der Potenz von 2 ist.
    Die maximale Anzahl erforderlich, um es auszudrücken, als eine Summe von die macht der 2 wird die Zahl selbst, weil Sie Ausdrücken können, als Summe von 1 ( weil 2 die Kraft 0 ist 1).
    Beispiel: 5 ausgedrückt werden kann als ( 1+1+1+1+1)

    daher die Gesamtzahl der Möglichkeiten zum Ausdruck bringen, eine Zahl als Potenz von 2 ist einfach gegeben durch die Formel -->
    lassen Sie das nicht sein x
    ( x - no der gesetzten bits in x ) + 1 ;
    lassen Sie zum Beispiel die Zahl 17
    die dann nicht von bits, die in 17 ist 2
    damit die keine Möglichkeiten gibt ( 17 - 2 ) + 1 = 16 ;

    InformationsquelleAutor shalini negi
Schreibe einen Kommentar