一个最大值问题

mathe

写了个程序计算了一下，7#在10以内数据都是正确的，但是对于15的结果不对，应该为:
28.245565[ 2.000000 0.500000 2.000000 0.500000 2.000000 0.500000 2.000000 0.5000
00 2.000000 0.500000 1.863636 0.500000 0.500000 0.500000 0.500000 ]
同样对于20也可以计算出来如下：
37.875287[ 2.000000 0.500000 2.000000 0.500000 2.000000 0.500000 2.000000 0.5000
00 2.000000 0.500000 2.000000 0.500000 2.000000 0.500000 1.933333 0.500000 0.500
000 0.500000 0.500000 0.500000 ]
所以现在最优的模式可以猜测为前面若干对2,0.5,后面若干连续0.5,中间隔一个待定数

mathe

1. #include <stdio.h>
   
2. #include <math.h>
   
3. #define N 15
   
4. int best_cand;
   
5. int best_t;
   
6. double maxv=0;
   
7. 
   
8. double value[N];
   
9. void lookup(int t)
   
10. {
    
11.         int i,j;
    
12.         double T=N*N/2.0;
    
13.         for(i=0;i<1<<N;i++){
    
14.                 for(j=0;j<N;j++){
    
15.                         if(i&(1<<j)){
    
16.                                 value[j]=2.0;
    
17.                         }else{
    
18.                                 value[j]=0.5;
    
19.                         }
    
20.                 }
    
21.                 double s=0.0;
    
22.                 for(j=0;j<N;j++){
    
23.                         if(j!=t){
    
24.                                 s+=value[j]*(j+1);
    
25.                         }
    
26.                 }
    
27.                 value[t]=s=(T-s)/(t+1);
    
28.                 if(s>=0.5&&s<=2.0){
    
29.                         s=0.0;
    
30.                         for(j=0;j<N-1;j++){
    
31.                                 s+=value[j]/value[j+1];
    
32.                         }
    
33.                         s+=value[N-1]/value[0];
    
34.                         if(s>maxv){
    
35.                                 maxv=s;
    
36.                                 best_t=t;
    
37.                                 best_cand=i;
    
38.                         }
    
39.                 }
    
40.         }
    
41. }
    
42. 
    
43. void decode()
    
44. {
    
45.         int j;
    
46.         double s=0.0;
    
47.         printf("%f[ ",maxv);
    
48.         for(j=0;j<N;j++){
    
49.                 if(best_cand&(1<<j)){
    
50.                         value[j]=2.0;
    
51.                 }else{
    
52.                         value[j]=0.5;
    
53.                 }
    
54.                 if(j!=best_t){
    
55.                         s+=value[j]*(j+1);
    
56.                 }
    
57.         }
    
58.         value[best_t]=(N*N/2.0-s)/(best_t+1);
    
59.         for(j=0;j<N;j++){
    
60.                 printf("%f ",value[j]);
    
61.         }
    
62.         printf("]\n");
    
63. }
    
64. 
    
65. int main()
    
66. {
    
67.         int i;
    
68.         for(i=0;i<N;i++){
    
69.                 lookup(i);
    
70.         }
    
71.         decode();
    
72.         return 0;
    
73. }

复制代码

mathe

10#分析了连续两个以上的0.5后面不可以出现连续的2
而同样，如果我们分析0.5 0.5 0.5 2 0.5,可以发现它不是最优的，因为0.5 2.0 0.5 c 0.5 (其中c=0.5+1.5/(k+2))可以替换它得到更好的结果。由此我们可以得到，只要出现连续3个以上0.5以后，后面将不可以出现2.

mathe

一个扩展的猜想，如果约束和由${n^2}/2$改成一个任意的正实数，是不是取最大值的地方必然是形如
2,2,...,2,u,2,0.5,2,0.5,...,2,0.5
或
2,0.5,2,0.5,..,2,0.5,u,0.5,0.5,...,0.5

数学星空

根据mathe的结论:
所以现在最优的模式可以猜测为前面若干对2,0.5,后面若干连续0.5,中间隔一个待定数
设待定数$u=a_(2k+1)$则可以推得$u=1/{4(2k+1)}*(n^2-n+2-(6k^2-4k))$现在的问题归结于求k值?
根据youyouyou提供的数值解有:
$n=4,5$ 时$ k=1$
$n=6,7$ 时$ k=2$
$n=8,9,10$时$ k=3$
$n=15$时$ k=5$(mathe)
$n=20$时$ k=7$(mathe)
谁能给出 k与n的关系? 进而就能求出最大值及对应的$a_i(1<=i<=n)$值了

数学星空

根据上面的结果可以得出最大值:$9/4*k+2*u+1/{2*u}+n-2$

数学星空

现将mathe的更一般猜想整理如下:
    已知$c<=a_i<=d $ $(0<c<d,i=1,2,.....,n)$ ,且满足:$a_1+2*a_2+3*a_3+.....+n*a_n=R*n^2$
则$a_1/a_2+a_2/a_3+a_3/a_4+.....a_(n-1)/a_n+a_n/a_1$取得最大值
当且仅当$(a_1,a_2,a_3,....,a_n)=(c,c,c,...,c,u,d,...,d)$
        或者$(a_1,a_2,a_3,....,a_n)=(d,c,...,d,c,u,c,...,c)$

按照上面的计算同样可以得到:
设$u=a_(2k+1)$
则$u=1/{2(2k+1)}*((2R-c)n^2-cn+2(c-d)k^2+2(2k+1)c)$
最大值为:$(d/c+c/d-2)k+(c/u+u/c)+n-2$

有谁能提供一些计算数据,得到k与n的关系?那么就解决了这个问题.
注: $1/2 (1/n+1)c<=R<=1/2(1/n+1)d$

mathe

根据mathe的结论:
所以现在最优的模式可以猜测为前面若干对2,0.5,后面若干连续0.5,中间隔一个待定数
设待定数u=a_(2k+1)则可以推得u=1/{4(2k+1)}*(n^2-n+2-(6k^2-4k))现在的问题归结于求k值?
根据youyouyou提供的 ...
数学星空 发表于 2010-5-22 23:15

这个k的计算其实不难，只要根据前面加权和为${n^2}/2$,而且$1/2<=u<=2$可以得出一个不等式，而这个不等式的整数解会正好唯一存在

数学星空

根据mathe的提示:
我们可以算出:
k=[$sqrt{1/{2(d-c)} ((2R-c)n^2-nc)} $]
当$c=1/2,d=2,R=1/2$时 k=[$ sqrt{(n^2-n)/6}$]
注: [x]为不大于x的最大整数