home

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

Four Square Identity ของออยเลอร์ใน C++

ในปัญหานี้ เราได้รับตัวเลขสองตัวและเราจำเป็นต้องค้นหาผลคูณของตัวเลขโดยใช้ Identity Four Square Identity ของออยเลอร์

ตัวตนสี่เหลี่ยมของออยเลอร์ เป็นวิธีการหาผลคูณของตัวเลขสองตัวซึ่งสามารถแสดงโดยใช้ผลรวมของ สี่กำลังสอง ของตัวเลขหากตัวเลขสามารถแสดงเป็นผลรวมของสี่เหลี่ยมจัตุรัสได้

ผลิตภัณฑ์ a * b สามารถแสดงเป็นผลรวมของสี่เหลี่ยมสี่ช่องได้หาก

a =x1 2 + x2 2 + x3 2 + x4 2
b =y1 2 + y2 2 + y3 2 + y4 2
a * b =z1 2 + z2 2 + z3 2 + z4 2

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล:

a =54 =2*2 + 3*3 + 4*4 + 5*5

b =10 =1*1 + 2*2 + 1*1 + 2*2


ผลลัพธ์: 1*1 + 1*1 + 3*3 + 23*23

คำอธิบาย:

ผลคูณของ a และ b =540

ซึ่งสามารถแสดงได้หลายวิธี เราจะพบวิธีแก้ปัญหาหนึ่งข้อที่นี่

540 =1*1 + 1*1 + 3*3 + 23*23 =1 + 1 + 9 + 529

แนวทางการแก้ปัญหา -

วิธีแก้ปัญหาอย่างง่ายคือการใช้วิธีทดลองเพื่อลองใช้ชุดค่าผสมสี่สี่เหลี่ยมแต่ละชุดเพื่อแก้ปัญหา สำหรับสิ่งนี้ เราจะใช้ nested loops, หนึ่ง nested loop สำหรับแต่ละค่ากำลังสอง จากนั้นหาค่าที่คำนวณและพิมพ์ผลรวมที่เป็นไปได้ทั้งหมด

วิธีแก้ปัญหานี้ค่อนข้างซับซ้อนและความซับซ้อนของเวลาเป็นของคำสั่ง
O( (a*b) 4 ).

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

void findEulerSquareNumberValue(int a, int b) {

   int prod = a * b;
   int sumSquare = 0;
   for (int x = 0; x <= sqrt(prod); x++) {
      for (int y = x; y <= sqrt(prod); y++) {
         for (int z = y; z <= sqrt(prod); z++) {
            for (int k = z; k <= sqrt(prod); k++) {
           
               sumSquare = (x*x) + (y*y) + (z*z) + (k*k);
               if (sumSquare == prod) {
                cout<<"The product "<<a<<"*"<<b<<" = "<<prod<<" represented as ";
                cout<<x<<"*"<<x<<" + ";
                cout<<y<<"*"<<y<<" + ";
                cout<<z<<"*"<<z<<" + ";
                cout<<k<<"*"<<k<<endl;
                cout<<endl;
               }
            }
         }
      }
   }
}

int main() {

   int a = (2*2) + (3*3) + (4*4) + (5*5);
   int b = (1*1) + (2*2) + (1*1) + (2*2);
   cout<<"a = (2*2) + (3*3) + (4*4) + (5*5) = "<<a<<endl;
   cout<<"b = (1*1) + (2*2) + (1*1) + (2*2) = "<<b<<endl;
   findEulerSquareNumberValue(a, b);
   
   return 0;
}

ผลลัพธ์ -

a = (2*2) + (3*3) + (4*4) + (5*5) = 54
b = (1*1) + (2*2) + (1*1) + (2*2) = 10
The product 54*10 = 540 represented as 1*1 + 1*1 + 3*3 + 23*23

The product 54*10 = 540 represented as 1*1 + 3*3 + 13*13 + 19*19

The product 54*10 = 540 represented as 1*1 + 5*5 + 15*15 + 17*17

The product 54*10 = 540 represented as 1*1 + 7*7 + 7*7 + 21*21

The product 54*10 = 540 represented as 1*1 + 9*9 + 13*13 + 17*17

The product 54*10 = 540 represented as 2*2 + 4*4 + 6*6 + 22*22

The product 54*10 = 540 represented as 2*2 + 4*4 + 14*14 + 18*18

The product 54*10 = 540 represented as 2*2 + 6*6 + 10*10 + 20*20

The product 54*10 = 540 represented as 2*2 + 12*12 + 14*14 + 14*14

The product 54*10 = 540 represented as 3*3 + 3*3 + 9*9 + 21*21

The product 54*10 = 540 represented as 3*3 + 7*7 + 11*11 + 19*19

The product 54*10 = 540 represented as 3*3 + 9*9 + 15*15 + 15*15

The product 54*10 = 540 represented as 3*3 + 11*11 + 11*11 + 17*17

The product 54*10 = 540 represented as 4*4 + 10*10 + 10*10 + 18*18

The product 54*10 = 540 represented as 5*5 + 5*5 + 7*7 + 21*21

The product 54*10 = 540 represented as 5*5 + 11*11 + 13*13 + 15*15

The product 54*10 = 540 represented as 6*6 + 6*6 + 12*12 + 18*18

The product 54*10 = 540 represented as 7*7 + 7*7 + 9*9 + 19*19

The product 54*10 = 540 represented as 7*7 + 9*9 + 11*11 + 17*17

The product 54*10 = 540 represented as 9*9 + 11*11 + 13*13 + 13*13

The product 54*10 = 540 represented as 10*10 + 10*10 + 12*12 + 14*14

อีก วิธีการแก้ปัญหาที่ใช้เวลาน้อยกว่าคือใช้การวนซ้ำ 3 วงและตรวจสอบค่าที่ออกมา หากจำนวนที่เหลือเป็นกำลังสองสมบูรณ์ ค่ารูทจะเป็นตัวเลขที่สี่ มิฉะนั้น จะไม่สามารถแก้ปัญหาได้ วิธีนี้อาจลบลูปที่สี่และทำให้โซลูชันมีประสิทธิภาพ

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

void findEulerSquareNumberValue(int a, int b) {

   int prod = a * b;
   int sumSquare = 0;
   for (int x = 0; x <= sqrt(prod); x++) {
      for (int y = x; y <= sqrt(prod); y++) {
         for (int z = y; z <= sqrt(prod); z++) {
         
            sumSquare = (x*x) + (y*y) + (z*z);
            float k = sqrt(prod - sumSquare);
            if ( floor(k) == ceil(k)) {
             cout<<"The product "<<a<<"*"<<b<<" = "<<prod<<" represented as ";
             cout<<x<<"*"<<x<<" + ";
             cout<<y<<"*"<<y<<" + ";
             cout<<z<<"*"<<z<<" + ";
             cout<<k<<"*"<<k<<endl;
             cout<<endl;
            }
         }
      }
   }
}

int main() {

   int a = (2*2) + (3*3) + (4*4) + (5*5);
   int b = (1*1) + (2*2) + (1*1) + (2*2);
   cout<<"a = (2*2) + (3*3) + (4*4) + (5*5) = "<<a<<endl;
   cout<<"b = (1*1) + (2*2) + (1*1) + (2*2) = "<<b<<endl;
   findEulerSquareNumberValue(a, b);
   
   return 0;
}

ผลลัพธ์ -

a = (2*2) + (3*3) + (4*4) + (5*5) = 54
b = (1*1) + (2*2) + (1*1) + (2*2) = 10
The product 54*10 = 540 represented as 1*1 + 1*1 + 3*3 + 23*23

The product 54*10 = 540 represented as 1*1 + 1*1 + 23*23 + 3*3

The product 54*10 = 540 represented as 1*1 + 3*3 + 13*13 + 19*19

The product 54*10 = 540 represented as 1*1 + 3*3 + 19*19 + 13*13

The product 54*10 = 540 represented as 1*1 + 3*3 + 23*23 + 1*1

The product 54*10 = 540 represented as 1*1 + 5*5 + 15*15 + 17*17

The product 54*10 = 540 represented as 1*1 + 5*5 + 17*17 + 15*15

The product 54*10 = 540 represented as 1*1 + 7*7 + 7*7 + 21*21

The product 54*10 = 540 represented as 1*1 + 7*7 + 21*21 + 7*7

The product 54*10 = 540 represented as 1*1 + 9*9 + 13*13 + 17*17

The product 54*10 = 540 represented as 1*1 + 9*9 + 17*17 + 13*13

The product 54*10 = 540 represented as 1*1 + 13*13 + 17*17 + 9*9

The product 54*10 = 540 represented as 1*1 + 13*13 + 19*19 + 3*3

The product 54*10 = 540 represented as 1*1 + 15*15 + 17*17 + 5*5

The product 54*10 = 540 represented as 2*2 + 4*4 + 6*6 + 22*22

The product 54*10 = 540 represented as 2*2 + 4*4 + 14*14 + 18*18

The product 54*10 = 540 represented as 2*2 + 4*4 + 18*18 + 14*14

The product 54*10 = 540 represented as 2*2 + 4*4 + 22*22 + 6*6

The product 54*10 = 540 represented as 2*2 + 6*6 + 10*10 + 20*20

The product 54*10 = 540 represented as 2*2 + 6*6 + 20*20 + 10*10

The product 54*10 = 540 represented as 2*2 + 6*6 + 22*22 + 4*4

The product 54*10 = 540 represented as 2*2 + 10*10 + 20*20 + 6*6

The product 54*10 = 540 represented as 2*2 + 12*12 + 14*14 + 14*14

The product 54*10 = 540 represented as 2*2 + 14*14 + 14*14 + 12*12

The product 54*10 = 540 represented as 2*2 + 14*14 + 18*18 + 4*4

The product 54*10 = 540 represented as 3*3 + 3*3 + 9*9 + 21*21

The product 54*10 = 540 represented as 3*3 + 3*3 + 21*21 + 9*9

The product 54*10 = 540 represented as 3*3 + 7*7 + 11*11 + 19*19

The product 54*10 = 540 represented as 3*3 + 7*7 + 19*19 + 11*11

The product 54*10 = 540 represented as 3*3 + 9*9 + 15*15 + 15*15

The product 54*10 = 540 represented as 3*3 + 9*9 + 21*21 + 3*3

The product 54*10 = 540 represented as 3*3 + 11*11 + 11*11 + 17*17

The product 54*10 = 540 represented as 3*3 + 11*11 + 17*17 + 11*11

The product 54*10 = 540 represented as 3*3 + 11*11 + 19*19 + 7*7

The product 54*10 = 540 represented as 3*3 + 13*13 + 19*19 + 1*1

The product 54*10 = 540 represented as 3*3 + 15*15 + 15*15 + 9*9

The product 54*10 = 540 represented as 4*4 + 6*6 + 22*22 + 2*2

The product 54*10 = 540 represented as 4*4 + 10*10 + 10*10 + 18*18

The product 54*10 = 540 represented as 4*4 + 10*10 + 18*18 + 10*10

The product 54*10 = 540 represented as 4*4 + 14*14 + 18*18 + 2*2

The product 54*10 = 540 represented as 5*5 + 5*5 + 7*7 + 21*21

The product 54*10 = 540 represented as 5*5 + 5*5 + 21*21 + 7*7

The product 54*10 = 540 represented as 5*5 + 7*7 + 21*21 + 5*5

The product 54*10 = 540 represented as 5*5 + 11*11 + 13*13 + 15*15

The product 54*10 = 540 represented as 5*5 + 11*11 + 15*15 + 13*13

The product 54*10 = 540 represented as 5*5 + 13*13 + 15*15 + 11*11

The product 54*10 = 540 represented as 5*5 + 15*15 + 17*17 + 1*1

The product 54*10 = 540 represented as 6*6 + 6*6 + 12*12 + 18*18

The product 54*10 = 540 represented as 6*6 + 6*6 + 18*18 + 12*12

The product 54*10 = 540 represented as 6*6 + 10*10 + 20*20 + 2*2

The product 54*10 = 540 represented as 6*6 + 12*12 + 18*18 + 6*6

The product 54*10 = 540 represented as 7*7 + 7*7 + 9*9 + 19*19

The product 54*10 = 540 represented as 7*7 + 7*7 + 19*19 + 9*9

The product 54*10 = 540 represented as 7*7 + 7*7 + 21*21 + 1*1

The product 54*10 = 540 represented as 7*7 + 9*9 + 11*11 + 17*17

The product 54*10 = 540 represented as 7*7 + 9*9 + 17*17 + 11*11

The product 54*10 = 540 represented as 7*7 + 9*9 + 19*19 + 7*7

The product 54*10 = 540 represented as 7*7 + 11*11 + 17*17 + 9*9

The product 54*10 = 540 represented as 7*7 + 11*11 + 19*19 + 3*3

The product 54*10 = 540 represented as 9*9 + 11*11 + 13*13 + 13*13

The product 54*10 = 540 represented as 9*9 + 11*11 + 17*17 + 7*7

The product 54*10 = 540 represented as 9*9 + 13*13 + 13*13 + 11*11

The product 54*10 = 540 represented as 9*9 + 13*13 + 17*17 + 1*1

The product 54*10 = 540 represented as 9*9 + 15*15 + 15*15 + 3*3

The product 54*10 = 540 represented as 10*10 + 10*10 + 12*12 + 14*14

The product 54*10 = 540 represented as 10*10 + 10*10 + 14*14 + 12*12

The product 54*10 = 540 represented as 10*10 + 10*10 + 18*18 + 4*4

The product 54*10 = 540 represented as 10*10 + 12*12 + 14*14 + 10*10

The product 54*10 = 540 represented as 11*11 + 11*11 + 17*17 + 3*3

The product 54*10 = 540 represented as 11*11 + 13*13 + 13*13 + 9*9

The product 54*10 = 540 represented as 11*11 + 13*13 + 15*15 + 5*5

The product 54*10 = 540 represented as 12*12 + 14*14 + 14*14 + 2*2