นับเลขกำลังสองและไม่ใช่กำลังสองก่อน n ใน C++

เราได้รับตัวเลข N เป้าหมายคือการหาคู่ที่เรียงลำดับของจำนวนบวกซึ่งผลรวมของลูกบาศก์ของมันคือ N

แนวทางที่ไร้เดียงสา

สำรวจตัวเลขทั้งหมดตั้งแต่ 1 ถึง N และตรวจสอบว่าเป็นกำลังสองสมบูรณ์หรือไม่ ถ้า floor(sqrt(i))==ceil(sqrt(i)).

จากนั้นตัวเลขจะเป็นกำลังสองสมบูรณ์

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

กำลังสองสมบูรณ์ด้านล่าง N สามารถพบได้โดยใช้สูตร:floor(sqrt(N))

มาทำความเข้าใจกับตัวอย่างกัน

ป้อนข้อมูล

N=20

ผลผลิต

Count of square numbers: 4
Count of non-square numbers: 16

คำอธิบาย

Square numbers are 1, 4, 9 and 16. Rest all are non-squares and less than 20.

ป้อนข้อมูล

N=40

ผลผลิต

Count of square numbers: 6
Count of non-square numbers: 34

คำอธิบาย

Square numbers are 1, 4, 9, 16, 25, 36. Rest all are non-squares and less than 40.

แนวทางที่ไร้เดียงสา

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

• เราหาจำนวนเต็ม N.

• ฟังก์ชัน squareNums(int n) รับ n และส่งกลับจำนวนตัวเลขที่ต่ำกว่า n ซึ่งเป็นกำลังสองสมบูรณ์หรือไม่ใช่กำลังสอง

• นับตัวแปรเริ่มต้นเป็น 0

• สำรวจโดยใช้ลูปจาก i=1 ถึง i<=n

• ถ้า floor(sqrt(i))==ceil(sqrt(i)) แสดงว่าจำนวนนั้นเป็นกำลังสองสมบูรณ์ ดังนั้นให้นับจำนวนที่เพิ่มขึ้น

• เมื่อสิ้นสุดการวนซ้ำทั้งหมด การนับจะมีจำนวนรวมที่เป็นกำลังสองสมบูรณ์

• N-squares จะเป็นตัวเลขที่ไม่ใช่กำลังสอง

ตัวอย่าง

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int squareNums(int n){
   int count = 0;
   for (int i = 1; i <= n; i++){
      if(floor(sqrt(i))==ceil(sqrt(i)))
         { count++; }
   }
   return count;
}
int main(){
   int N = 40;
   int squares=squareNums(N);
   cout <<endl<<"Count of squares numbers: "<<squares;
   cout <<endl<<"Count of non-squares numbers: "<<N-squares;
   return 0;
}

ผลลัพธ์

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

Count of squares numbers: 6
Count of non-squares numbers: 34

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

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

• เราหาจำนวนเต็ม N.

• ใช้ตัวแปรสี่เหลี่ยม =floor(sqrt(N))

• สี่เหลี่ยมแปรผันจะมีกำลังสองสมบูรณ์จำนวนหนึ่งต่ำกว่า N

• N-squares จะเป็นจำนวนของ non-squares ที่ต่ำกว่า N.

ตัวอย่าง

#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(){
   int N = 40;
   int squares=floor(sqrt(N));
   cout <<endl<<"Count of squares numbers: "<<squares;
   cout <<endl<<"Count of non-squares numbers: "<<N-squares;
   return 0;
}

ผลลัพธ์

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

Count of squares numbers: 6
Count of non-squares numbers: 34