給出「N」發現p和q使得p + q = N和p * q是最大的

Question

我需要我提出的粗略解決方案背後的邏輯/想法。

的問題是：

鑑於N，其中1<=N<=1000000
現在我需要找到兩個數p和q，使得p + q = N && p * q = maximum.

我選擇使用此(((N+1)/2)*((N/2)));基本上給了我最大的產品，最小的總和。但我對這種邏輯的證明感興趣。

任何幫助或建議？

#include<stdio.h> 

typedef unsigned long uint; 
unsigned long calc(uint); 

int main(void) { 
    short i = 0; 
    uint k = 0; 
    scanf("%i", &i); 
    while(i--) { 
     scanf("%lu", &k); 
     printf("%lu\n", calc(k)); 
    } 
    return 0; 
} 

uint calc(uint k){ 
    return (((k+1)/2)*((k/2))); 
} 

Answer 1

讓

f(p) = p * (N - p) = p * N - p^2 

然後：

f'(p) = N - 2 * p 
f''(p) = - 2 

由於f''(p) < 0，只是解決了f'(p) = 0給了我們一個地方最大值。

When f'(p) = 0, 
p = N/2 
=> q = N/2 

您還需要測試端點f(0)和f(N)，但是這兩種評估爲零，所以我們的最大值是全球最大。

注意：這基本上是說，在一定周長的所有矩形中，正方形具有最大的面積。