Computer >> Máy Tính >  >> Lập trình >> C ++

Giảm mảng thành một số nguyên duy nhất với hoạt động đã cho trong C ++

Cho một biến số nguyên làm đầu vào. Chúng ta hãy xem xét một mảng chứa các phần tử trong phạm vi từ 1 đến Số theo thứ tự bất kỳ. Nếu chúng ta thực hiện một phép toán Number-1 lần trên một mảng sao cho

  • Chúng tôi chọn hai phần tử A và B từ mảng

  • Xóa A và B khỏi mảng

  • Thêm tổng bình phương của A và B vào mảng

Cuối cùng chúng ta sẽ nhận được một giá trị số nguyên duy nhất; mục tiêu là tìm giá trị lớn nhất có thể cho phần tử đó.

Sử dụng Hàng đợi Ưu tiên

  • Để tối đa hóa kết quả cuối cùng, chúng ta sẽ phải chọn A và B sao cho chúng là tối đa.

  • Để tìm A và B tối đa, chúng tôi sẽ sử dụng một hàng đợi ưu tiên để lưu trữ các giá trị của các phần tử bên trong nó.

  • Hàng đợi ưu tiên lưu trữ các phần tử theo thứ tự giảm dần.

  • Phần tử trên cùng là phần tử có giá trị lớn nhất, v.v. Vì vậy, sau khi bật hai phần tử, chúng tôi sẽ đẩy các ô vuông của chúng vào hàng đợi một lần nữa.

  • Sẽ bật và đẩy Số - 1 lần để nhận được kết quả mong muốn.

Ví dụ

Đầu vào - Số =2

Đầu ra - Phần tử đơn sau khi giảm mảng:5

Giải thích - Giả sử chúng ta có các phần tử trong mảng là [1 2]

Sau khi chèn vào Hàng đợi Ưu tiên-:2 1

A =5, B =4:A 2 + B 2 =1 + 4 =5

Phần tử cuối cùng:5

Đầu vào - Số =5

Đầu ra - Phần tử đơn sau khi giảm mảng:5

Giải thích - Giả sử chúng ta có các phần tử trong mảng là [5 1 2 4 3]

Sau khi chèn vào Hàng đợi Ưu tiên-:5 4 3 2 1

A =5, B =4:A 2 + B 2 =25 + 16 =41:41 3 2 1

A =41, B =3:A 2 + B 2 =1681 + 9 =1690:1690 2 1

A =1690, B =2:A 2 + B 2 =1681 + 4 =2856104:2856104 1

A =2856104, B =1:A 2 + B 2 =1187163712 + 1 =1187163713:1187163713

Phần tử cuối cùng:1187163713

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Trong cách tiếp cận này, chúng ta sẽ ưu tiên hàng đợi để lưu trữ các phần tử của mảng theo thứ tự giảm dần. Bật đầu hai phần tử lớn nhất và đẩy tổng bình phương của cả hai vào hàng đợi đó một lần nữa. Làm điều này cho đến khi chỉ còn lại một giá trị duy nhất.

  • Lấy biến đầu vào là Số.

  • Lấy kiểu dữ liệu cho kết quả là số nguyên dài - lli

  • Hàm ReduceArray (int Num) nhận số đầu vào và trả về số nguyên đơn tối đa được tính bằng các phép toán trên.

  • Nhận hàng đợi ưu tiên là pQueue.

  • Điền pQueue với các số từ 1 đến N bằng vòng lặp while.

  • Trong khi tôi <=Num, hãy đẩy tôi đến pQueue

  • Bây giờ pQueue có các số nguyên từ 1 đến N theo thứ tự giảm dần và kích thước là N.

  • Bây giờ duyệt qua pQueue bằng cách sử dụng một vòng lặp while cho đến khi kích thước của nó là> =1.

  • Lấy giá trị tối đa là var1 =pQueue.top () và bật nó lên.

  • Lấy giá trị tối đa tiếp theo là var2 =pQueue.top () và bật nó lên.

  • Đặt var1 làm hình vuông và var2 làm hình vuông.

  • Đẩy lại var1 + var2 đến pQueue.

  • Ở cuối vòng lặp while, trả về phần tử trên cùng.

  • In kết quả bên trong main.

Ví dụ 

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
int reduceArray(int Num){
   priority_queue<lli> pQueue;
   int i=1;
   while(i<=Num){
      pQueue.push(i);
      i=i+1;
   }
   while (pQueue.size() > 1) {
      lli var1 = pQueue.top();
      pQueue.pop();
      lli var2 = pQueue.top();
      pQueue.pop();
      var1=var1*var1;
      var2=var2*var2;
      pQueue.push(var1+var2);
   }
   return pQueue.top();
}
int main(){
   int Number = 5;
   cout<<"Single element after array reduction: "<<reduceArray(Number);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau 

Single element after array reduction: 1187163713