Đa giác số - thuật toán và cài đặt bằng C/C++

Đa giác số - thuật toán và cài đặt bằng C/C++

Trên vòng tròn đánh dấu n điểm phân biệt. Các điểm này được chọn làm n đỉnh của đa giác lồi P. Vẽ tất cả các đường chéo của đa giác P. Cho N là một họ gồm n số nguyên dương. Mỗi số của họ N sẽ được viết bên cạnh một đỉnh của đa giác P. Ta gọi việc làm này là phân bố các số của họ N cho các đỉnh của đa giác P. Tiếp theo, mỗi đường chéo của đa giác P sẽ được gán cho một số nguyên bằng tích của hai số gán cho đỉnh đầu mút của nó.

Ví dụ: n = 7, N = <15, 12, 2, 12, 10, 11, 10>. Một cách phân bố các số của họ N cho các đỉnh của đa giác được chỉ ra trong hình vẽ dưới đây:

Yêu cầu: Tìm cách phân bố các số của họ N cho các đỉnh của đa giác sao cho tổng các số gán cho các đường chéo là lớn nhất.

Dữ liệu: Vào từ file văn bản NUMPOLY.INP:

  • Dòng đầu tiên chứa số nguyên n (3 < n ≤ 105).
  • Dòng thứ hai chứa n số nguyên dương của họ N, mỗi số không vượt quá 106, hai số liên tiếp phân tách nhau bởi dấu cách.

Kết quả: Ghi ra file văn bản NUMPOLY.OUT 5 chữ số cuối cùng của tổng các số gán trên đường chéo theo cách phân bố tìm được. Chú ý là file kết quả phải chứa đúng 5 chữ số (như vậy, số gồm 5 chữ số trên file kết quả có thể có các số 0 đứng đầu).

NUMPOLY.INP

NUMPOLY.OUT

7

15 12 2 12 10 11 10

01487

Giải thích: Cách phân bố cho trong hình vẽ minh họa ở trên có tổng các số gán cho đường chéo là số có tận cùng bởi 5 chữ số ‘01487’.

Phát biểu lại bài toán:

  • Cho N số nguyên: a0, a1,…, an-1 (3 < n ≤10^5);
  • Tìm cách phân bố n số cho các đỉnh của đa giác n đỉnh sao cho tổng các số gán cho các đường chéo ( bằng tích của hai số ở hai đỉnh đầu mút) là lớn nhất.

Giải thuật

  • Ta có khai triển: (SUM(ai))^2 = SUM((ai)^2) + 2* SUM(ai*a(i+1)mod n) + 2* SUM(ai*aj); trong đó  i = 0 to n-1
  • Ta tính được bình phương tổng của các số (ký hiệu là ∑) và tổng các bình phương của các số S1, nên nếu ký hiệu S2 là tổng của tích các cặp số liên tiếp thì tổng các số trên đường chéo S được tính bởi công thức sau: S = (∑ - S1 – 2S2)/2.
  • Từ đó suy ra bài toán dẫn về tìm cực tiểu tổng S1.
  • Nhận xét này cho phép giảm độ phức tạp, bởi vì số lượng đường chéo là n(n-3)/2, trong đó n là số đỉnh của đa giác.
  • Hơn nữa, ta có thuật toán đơn giản đê tìm cấu hình cho cực tiểu tổng S1: Sắp xếp các số a1, sau đó bắt đầu từ hai đầu dãy, tiến hành hoán đổi các số và dịch chuyển sang bên cạnh: phái trái dịch từ trái sang phải, phái phải dịch từ phải sang trái cho đến khi chờm qua nhau. Khi phân bố chú ý tiến hành tính chỉ số theo model.

Chương trình cài đặt:

#include <cstdio>

#include <iostream>

#include<stdlib.h>

#include<conio.h>

using namespace std;

#define nmax 1000000

int array[nmax];

unsigned long long sum;

unsigned long long SIGMA, sigma, sumS1;

int compare(const void * a, const void * b)

{

 return (*(int*)a - *(int*)b);

}

int main(int argc, char** argv)

{

 freopen("NUMPOLY.INP", "r", stdin);

 freopen("NUMPOLY.OUT", "w", stdout);



 int n;

 cin >> n;

 for (int i = 0; i < n; i++){

  cin>> array[i];

  SIGMA += array[i];

  sigma += array[i] * array[i];

 }

 SIGMA *= SIGMA;

 qsort(array, n, sizeof(int), compare);

 

 for (int i = 1; i < n/2; i = i+ 2){

  int temp = array[i];

  array[i] = array[n - 1 - i];

  array[n - 1 - i] = temp;

 }

 for (int i = 0; i < n; i ++){

  sumS1 += (unsigned long long) array[i] * array[(i + 1) % n];

 }


 sum = (unsigned long long)(SIGMA - sigma - 2 * sumS1) / 2;

 if (sum < 10){

  cout << "0000" << sum;

 }

 else if (sum < 100){

  cout << "000" << sum;

 }

 else if (sum < 1000){

  cout << "00" << sum;

 }

 else if (sum < 10000){

  cout << "0" << sum;

 }

 else{

  cout<< sum%100000;

 }

 

 return 0;

}

 

Bạn thấy bài viết này như thế nào?: 
Average: 10 (6 votes)
Ảnh của Tommy Tran

Tommy Tran owner Express Magazine

Drupal Developer having 9+ year experience, implementation and having strong knowledge of technical specifications, workflow development. Ability to perform effectively and efficiently in team and individually. Always enthusiastic and interseted to study new technologies

  • Skype ID: tthanhthuy
  • Phone/Zalo: (+84) 944 225 212
  • WhatsApp: (+84) 944 225 212
  • Line Messenger: (+84) 944 225 212
  • Email: asaleotestf@gmail.com
  • Telegram Messenger: https:/t.me/tommytran0401

Quảng cáo việc làm

 

Thích hợp các bạn nữ mảng thợ may làm việc tại nước NGA

Đơn hàng Tuyển dụng 100 Thợ may đi Nga(đợt 1 tháng 3.2021, đợt 2 tháng 5.2021). Lương thực lãnh 800 USD, bao ăn ở, vé máy bay và visa, phí xuất cảnh(1800 USD)trả khi đi làm có lương. Bạn có thể liên hệ CÔNG TY qua Phone/Zalo: (+84) 944 225 212. Công ty sẽ tư vấn cho bạn.

Xem chi tiết: >>> https://bit.ly/3o9NOfR

Advertisement

 

jobsora

Dich vu khu trung tphcm

Dich vu diet chuot tphcm

Dich vu diet con trung

Quảng Cáo Bài Viết

 
Best To Do Apps for Android Phones

Best To Do Apps for Android Phones

Android phones are lovely little gadgets that make your life absolutely fun, simply because they can do so many things that other phones cannot.

Thủ thuật đếm total Number cho Disqus Comments trong Page in Drupal 7

Thủ thuật đếm total Number cho Disqus Comments trong Page in Drupal 7

On a recent project I had to show the total number of comments posted using Disqus for each node on a page. What the page did was loop through a bunch of nodes and render the teaser view of each node.

 www.studentunion.okstate.edu

Mô tả dự án: studentunion (dot) okstate (dot) edu

Serving over 22,000 students, in addition to OSU faculty and staff, the Student Union serves as a hub for campus life and is easily one of the busiest places on campus.

BLOG POSTS