Birlerin ve İkilerin Toplamıyla Sayı Oluşturmanın Yolları

Aug 16 2020

Sadece birleri ve ikilileri kullanarak bir sayıyı toplamanın olası yollarını saymanın bir yolu olup olmadığını merak ediyorum.

Örneğin:

10 numaramız var. 10 rakamı şu şekilde özetlenebilir:

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1  
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2
2 + 2 + 2 + 2 + 2 
etc...

Şimdiden teşekkür ederim!

Yanıtlar

1 amit Aug 17 2020 at 03:22

Öğelerin sırası önemli değilse, yorumlarda açıklandığı gibi (yani 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2aynı ise 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), bu basitçe toplamdaki öğe sayısını seçmektir, bu sayı 5 ila 10 arasında herhangi bir yerde olabilir. kaç tanesinin 1s ve kaçının 2s olması gerektiğini tam olarak bilin: x elemanlar için 10-x 2s ve geri kalanlar 1s.

Aralarından seçim yapabileceğiniz 6 numara olduğundan, bu, 10 oluşturmanın yollarının sayısıdır.

another_CS_guy Aug 17 2020 at 05:36

Karmaşık matematiksel formüllere girmek yerine, DP yaklaşımını tavsiye ederim.


    int arr[N+1]; // Represents no. of ways to produce a number at index 1
    // Like arr[5] is no. of ways to produce number 5
    
    for(int i=0;i<=N;i++) {
      arr[i] = 1; // As all 1s
    }
    
    for(int i=2;i<=N;i++) {
      // if we add 2 now, check for no. of ways i-2 can be made, 
      // add it to current arr[i] value.
      arr[i] += arr[i-2];
    }
    
    cout<< (arr[N]); // print

RahulBhobe Aug 17 2020 at 18:07

Yalnızca birleri kullanarak sayı oluşturmanın yollarının sayısı = 1
En az bir iki kullanarak sayı oluşturmanın yollarının sayısı = floor(n/2)
Toplam =1 + floor(n/2)

Aşağıdaki javascriptkod parçasına bakın:

let numWays = n => 1 + Math.floor(n/2);

for (let i=1; i<=20; i++)
    console.log("Number of ways to create " + i + " is: " + numWays(i));