Đ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: [email protected]
  • Telegram Messenger: https:/t.me/tommytran0401

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

 
[Google] Hướng dẫn đăng ký Google AdSense

[Google] Hướng dẫn đăng ký Google AdSense

Google AdSense là một mạng quảng cáo trung gian uy tín của Google dành cho các Publisher và Advertiser, trong bài viết này mình chỉ đề cập tới Publisher, tức là dành cho các chủ website bán quảng cáo trên trang web của mình.

Phần 1: Apache Solr - Hướng dẫn Creating Custom Fields

This is the first of two blog posts. In this one I will show you how to create a custom search index in Apache Solr

SEO

Những yếu tố xếp hạng sẽ giảm ‘trọng lượng’ trong năm 2012

Có lẽ năm vừa qua SEO đã có 1 chuyển biến khá lớn khi bắt đầu chiến dịch Panda và các mirror mở rộng tầm ảnh hưởng. Trong đó các yếu tố SEO có những thay đổi và Google dần trở nên thông minh hơn khi thay đổi độ mạnh và yếu của các yếu tố này. Đặc biệt những yếu tố sau đây nó đã dần mất ưu thế và tất nhiên bạn cũng nên xem lại những yếu tố này để không phải quá chú trọng vào nó:

Wordpress Freelancer

 

Wordpress Freelancer