จำนวนคู่ของ (i, j) ที่ ((n % i) % j) % n ถูกขยายให้ใหญ่สุดใน C++

เราได้รับตัวเลขเป็นอินพุต เป้าหมายคือการหาจำนวนคู่ของรูปแบบ (i,j) ที่ ((num%i)%j)%num ถูกขยายให้ใหญ่สุด และ i และ j ทั้งคู่อยู่ในช่วง [1,num]

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

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

ผลผลิต − จำนวนคู่ของ (i, j) โดยที่ ((n % i) % j) % n ถูกขยายให้ใหญ่สุดคือ − 3

คำอธิบาย − คู่จะเป็น:(3,2), (3,3), (3,4)

ป้อนข้อมูล − num=6

ผลผลิต − จำนวนคู่ของ (i, j) โดยที่ ((n % i) % j) % n ถูกขยายให้ใหญ่สุดคือ − 4

คำอธิบาย − คู่จะเป็น:(4,3, (4,4), (4,5), (4,6)

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

เราจะแก้ปัญหานี้โดยใช้สองวิธี ในแนวทางที่ไร้เดียงสา สามารถรับค่าที่เหลือสูงสุดได้หากเรามี num เป็นครึ่งหนึ่ง ตั้งอุณหภูมิ=num/2 +1 ตั้งค่าส่วนที่เหลือสูงสุดเป็น total=num%temp สำรวจหา i,j จาก 0 ถึง num และพบว่า i,j นั้น ((num % i) % j) % num ==Total.

• รับอินพุตเป็นจำนวนเต็ม

• ฟังก์ชันขยายใหญ่สุด_pair(int num) รับ num และส่งกลับจำนวนคู่ของ (i, j) เพื่อให้ ((n % i) % j) % n ถูกขยายให้ใหญ่สุด

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

• ลด num เหลือครึ่งหนึ่งสำหรับส่วนที่เหลือสูงสุด ตั้งอุณหภูมิ =((num / 2) + 1).

• คำนวณส่วนที่เหลือสูงสุดเป็นผลรวม =num % temp;

• สำหรับคู่ (i,j) สำรวจโดยใช้สองลูปสำหรับ i และ j ในช่วง [1,num].

• ถ้าค่า ((num % i) % j) % num เท่ากับยอดทั้งหมด ให้นับเพิ่ม

• ที่ส่วนท้ายของทั้งสอง for loops ผลตอบแทนจะนับเป็นผลลัพธ์

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

รับ ยอดรวมสูงสุด =num % temp โดยที่ อุณหภูมิคือ num/2+1 . ตอนนี้สำหรับคู่ (i,j) เราต้องเลือก i เป็น num เพื่อให้ได้ค่าที่เหลือสูงสุด เราสามารถเลือก j จากช่วง ผลรวม ถึง num เพื่อให้ยอดรวมสูงสุด ดังนั้นการนับคู่จะเป็น จำนวนรวม .

ในกรณีที่ num=2 ให้คืนค่า 4 เป็นคู่ (1,1), (1,2), (2,1), (2,2) และจะไม่คำนวณโดยใช้ num-total

• รับอินพุตเป็นจำนวนเต็ม

• ฟังก์ชันขยายใหญ่สุด_pair(int num) รับ num และส่งกลับจำนวนคู่ของ (i, j) เพื่อให้ ((n % i) % j) % n ถูกขยายให้ใหญ่สุด

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

• ถ้า num==2 ให้คืนค่า 4

• อย่างอื่นลด num ลงครึ่งหนึ่งสำหรับส่วนที่เหลือสูงสุด ตั้งอุณหภูมิ =((num / 2) + 1).

• คำนวณส่วนที่เหลือสูงสุดเป็นผลรวม =num % temp;

• ตั้งค่า count=num-total

• เมื่อสิ้นสุดผลตอบแทนนับเป็นผลลัพธ์

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

#include<bits/stdc++.h>
using namespace std;
int maximized_pair(int num){
   int count = 0;
   int temp = ((num / 2) + 1);
   int total = num % temp;
   for (int i = 1; i <= num; i++){
      for (int j = 1; j <= num; j++){
         int check = ((num % i) % j) % num;
         if (check == total){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int num = 10;
   cout<<"Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: "<<maximized_pair(num);
}

ผลลัพธ์

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

Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: 6

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

#include<bits/stdc++.h>
using namespace std;
int maximized_pair(int num){
   int count = 0;
   if (num == 2){
      return 4;
   }
   else{
      int temp = ((num / 2) + 1);
      int total = num % temp;
      count = num - total;
   }
   return count;
}
int main(){
   int num = 10;
   cout<<"Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: "<<maximized_pair(num);
}

ผลลัพธ์

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

Count of pairs of (i, j) such that ((n % i) % j) % n is maximized are: 6