home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

นับจำนวนเต็มบวกด้วย 0 เป็นหลักและสูงสุด 'd' หลักใน C++

เราได้รับตัวเลข d ซึ่งแสดงถึงจำนวนหลัก เป้าหมายคือการหาจำนวนเต็มบวกที่มี 0 เป็นหลักและมีตัวเลขสูงสุด d หลัก นับทั้งหมด 1 หลัก 2 หลัก 3 หลัก….d ตัวเลขบวกที่มี 0 อย่างน้อยหนึ่งตัว

ขั้นแรกเราจะหาจำนวน นับจำนวนตัวเลขที่มี d หลัก อย่างน้อยหนึ่ง 0 สมมติว่า d=3 หากต้องการสร้างตัวเลข 3 หลักที่มีอย่างน้อย 0 อย่างน้อย วิธีที่ทำได้คือ −

นับจำนวนเต็มบวกด้วย 0 เป็นหลักและสูงสุด d หลักใน C++ 

Here d1 can have 1 to 9 : 9 ways
d2 can have 0-9 : 10 ways
d3 can have 0-9 : 10 ways
Total numbers possible: 9 x 10 x 10 = 9 x 102
For d digits, count of numbers: 9 x 10d-1
For d digits, numbers without any 0 are : 9d
Total numbers having d digits with at least one 0 = 9 x 10d-1 - 9d = 9 x ( 10d-1 - 9d-1 )

ให้เราเข้าใจด้วยตัวอย่าง

ป้อนข้อมูล − d=4

ผลผลิต − นับจำนวนเต็มบวกที่มี 0 เป็นหลัก และหลัก 'd' สูงสุดคือ − 2619

คำอธิบาย − x ตัวเลขที่มี 0 อย่างน้อยหนึ่งตัว −

1 digit numbers : 0
2 digit numbers : 9
3 digit numbers : 171
4 digit numbers: 2439
Total= 9+171+2439 = 2619

ป้อนข้อมูล − d=1

ผลผลิต − การนับจำนวนเต็มบวกที่มี 0 เป็นหลัก และหลัก 'd' สูงสุดคือ − 0

คำอธิบาย − 1 ถึง 9 ไม่มีตัวเลขใดที่มี 0 เป็นหลัก

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

เราจะใช้สองวิธี แนวทางที่ไร้เดียงสาครั้งแรกโดยใช้ a for a loop เริ่มการข้ามจาก 1 หลักถึง d หลักและคำนวณตัวเลขโดยใช้สูตรที่กล่าวถึงข้างต้น เพิ่มมูลค่าที่ส่งคืนเพื่อนับ

  • นำจำนวนเต็ม d มาเป็นตัวเลข

  • ฟังก์ชัน total_count(int d)) ใช้จำนวนหลัก d และส่งกลับจำนวนตัวเลขที่มี d หลักที่มี 0 อย่างน้อยหนึ่งตัว

  • คำนวณตัวเลขเช่น temp=9*(pow(10,d-1) - pow(9,d-1));

  • อุณหภูมิขากลับ

  • ฟังก์ชัน maximum_d(int d) ใช้จำนวนสูงสุดของหลัก d และส่งกลับจำนวนตัวเลขไม่เกิน d หลักที่มี 0 อย่างน้อยหนึ่งตัว

  • สำรวจโดยใช้การวนซ้ำโดยเริ่มจากตัวเลข 1 หลัก ตามด้วย 2 ไปเรื่อยๆ จนถึง d

  • สำหรับแต่ละ d คำนวณตัวเลขเป็น total_count(i) เพิ่มสิ่งนี้เพื่อนับ

  • ในที่สุดเราก็ได้ยอดรวมแล้ว

  • ผลตอบแทนนับเป็นผลลัพธ์

แนวทางที่มีประสิทธิภาพ

ในวิธีนี้ เราจะคำนวณการนับโดยสังเกต G.P ที่เกิดขึ้นสำหรับการคำนวณข้างต้น

Solution is 9 x (10d-1 - 9d-1)
= 9 x (10d - 1)- 9 x (9d-1)
= 9 x (10i - 1) - 9 x (9i - 1) ( 1<=i<=d )
= g.p 1 - g.p 2
= 9x(10d-1)/(10-1) - 9x(9d-1)/(9-1)
= (10d-1)- (9/8)*(9d-1)

  • นำ d เป็นจำนวนหลักสูงสุด

  • ฟังก์ชัน maximum_d(int d) ใช้จำนวนสูงสุดของหลัก d และคืนค่าการนับจำนวนตัวเลขสูงสุด d หลักที่มี 0 อย่างน้อยหนึ่งตัว

  • ใช้สูตรข้างต้นคำนวณ temp_1 เป็น 9*((pow(10,d)-1)/9)

  • คำนวณ temp_2 เป็น 9*((pow(9,d)-1)/8)

  • ตั้งค่าการนับ =temp_1 - temp_2.

  • ผลตอบแทนนับเป็นผลลัพธ์

ตัวอย่าง (แนวทางไร้เดียงสา)

#include<bits/stdc++.h>
using namespace std;
int total_count(int d){
   int temp = 9*(pow(10,d-1) - pow(9,d-1));
   return temp;
}
int maximum_d(int d){
   int count = 0;
   for (int i=1; i<=d; i++){
      count = count + total_count(i);
   }
   return count;
}
int main(){
   int d = 5;
   cout<<"Count of positive integers with 0 as a digit and maximum 'd' digits are: "<<maximum_d(d) << endl;
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of positive integers with 0 as a digit and maximum 'd' digits are: 33570

ตัวอย่าง (แนวทางที่มีประสิทธิภาพ)

#include<bits/stdc++.h>
using namespace std;
int maximum_d(int d){
   int temp_1 = 9*((pow(10,d)-1)/9);
   int temp_2 = 9*((pow(9,d)-1)/8);
   int count = temp_1 - temp_2;
   return count;
}
int main(){
   int d = 4;
   cout<<"Count of positive integers with 0 as a digit and maximum 'd' digits are: "<<maximum_d(d) << endl;
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of positive integers with 0 as a digit and maximum 'd' digits are: 2619