Đ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 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

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

 
Hiển thị Bootstrap Components sử dụng Views Bootstrap

Hiển thị Bootstrap Components sử dụng Views Bootstrap

Bootstrap is a mobile first front-end framework that allows a developer to build websites quickly. The framework comes with a lot of reusable CSS styles, components and jQuery plugins.

Nofollow là gì? Cách xây dựng Backlinks

Một trong những kỹ thuật SEO, để gia tăng thứ hạng cho website đó là “Xây dựng Backlinks” nếu site của bạn được những site có thứ hạng cao liên kết tới, bạn sẽ được Search Engines tìm đến nhanh hơn.

Lâm Đào Trúc Anh, học sinh lớp 12 Văn trường Phổ thông Năng khiếu - Đại học Quốc gia TP HCM

Lâm Đào Trúc Anh giành 12 học bổng trị giá gần 1,8 triệu USD

Đỗ hai trường ở Mỹ và Canada, Lâm Đào Trúc Anh còn được 12 đại học khác cấp học bổng với tổng trị giá gần 1,8 triệu USD - khoảng 42 tỷ đồng.

Tomdesgin.vn

 

Drupal Services