วิธีสร้างตัวเลขด้วยผลรวมของคนและสองคน

Aug 16 2020

ฉันสงสัยว่ามีวิธีนับวิธีที่เป็นไปได้ในการรวมจำนวนโดยใช้เพียงตัวเดียวและสองตัว

ตัวอย่างเช่น:

เรามีหมายเลข 10 หมายเลข 10 สามารถสรุปได้โดย:

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...

ขอบคุณทุกคนล่วงหน้า!

คำตอบ

1 amit Aug 17 2020 at 03:22

หากลำดับขององค์ประกอบไม่สำคัญดังที่ความคิดเห็นอธิบาย (เช่น1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2เหมือนกัน2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1) นี่เป็นเพียงการเลือกจำนวนองค์ประกอบในการสรุปซึ่งอาจอยู่ระหว่าง 5 ถึง 10 เมื่อเลือกจำนวนองค์ประกอบแล้วคุณ รู้ว่ามันต้องเป็น 1s กี่ตัวและต้องเป็น 2s กี่ตัว: สำหรับองค์ประกอบ x มี 10-x 2s และที่เหลือคือ 1s

เนื่องจากมี 6 หมายเลขให้เลือกนี่คือจำนวนวิธีในการสร้าง 10

another_CS_guy Aug 17 2020 at 05:36

แทนที่จะใช้สูตรทางคณิตศาสตร์ที่ซับซ้อนฉันขอแนะนำวิธี DP


    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

จำนวนวิธีในการสร้างตัวเลขโดยใช้เพียงอย่างเดียว = 1
จำนวนวิธีในการสร้างตัวเลขโดยใช้อย่างน้อยหนึ่งสอง = floor(n/2)
ผลรวม =1 + floor(n/2)

ดูjavascriptข้อมูลโค้ดด้านล่าง:

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));