爬山问题

iseemu2009

爬山问题

northwolves

第n个山峰的坐标很好求，问题是什么情况下看不到呢？直觉需要斜率的动态比较

KeyTo9_Fans

山峰的高度和山谷的深度形成的数列是这个：

https://oeis.org/A008347

山峰好像是上凸的，能看到的基本上都是近处的山峰，远处的山峰好像基本上都看不到

mathe

从复杂度来说，对于现在的计算机，$10^5$不大，直接计算每个点同后面所有点的仰角并进行比较是否超过当前已知最大仰角即可。
当然从效率上，应该需要考虑Fans提到的基本上都是近峰的问题，所以可以缩小计算数目。如果当前仰角正切值已经大于后面最大素数gap/两素数和，那么就不需要继续搜索了，不知道这个裁剪效率如何

iseemu2009

下面的程序计算前15个山峰的坐标

1. zb[n_] := {Total[Prime[Range[2 n - 1]]],
   
2.                    Total[Table[(-1)^(i - 1) Prime[i], {i, 2 n - 1}]]};(*计算第n个峰顶的坐标*)
   
3.                    dianji = Table[zb[i], {i, 15}]  (*计算前15个峰顶（点集）的坐标*)

复制代码

1. {2, 2}, {10, 4}, {28, 8}, {58, 12}, {100, 16}, {160, 18}, {238, 22}, {328, 26}, {440, 32}, {568, 38}, {712, 40}, {874, 44}, {1060, 52}, {1264, 54}, {1480, 56}

复制代码

mathe

52462

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define MAXP 2750200L
   
5. #ifndef MPS
   
6. #define MPS 20000
   
7. #endif
   
8. unsigned char notp[MAXP];
   
9. int pc;
   
10. long plist[MPS];
    
11. long sumf[MPS/2];
    
12. long sumg[MPS/2];
    
13. int maxslop[MPS/2];
    
14. 
    
15. #define ISPRIME(x) (!notp[x])
    
16. #define UNSETPRIME(x) (notp[x]=1)
    
17. 
    
18. void initp()
    
19. {
    
20.   UNSETPRIME(0);
    
21.   UNSETPRIME(1);
    
22.   long i;
    
23.   plist[pc++]=0;//add an extra number 0 at the beginning
    
24.   for(i=2;i<MAXP;i++){
    
25.     if(ISPRIME(i)){
    
26.       long j;
    
27.       plist[pc++]=i;
    
28.       if(pc>=MPS)break;
    
29.       for(j=i*i;j<MAXP;j+=i)UNSETPRIME(j);
    
30.     }
    
31.   }
    
32.   if(pc<MPS){
    
33.     fprintf(stderr,"Prime not enough\n");
    
34.     exit(-1);
    
35.   }
    
36.   sumf[MPS/2-1]=plist[MPS-1]+plist[MPS-2];
    
37.   sumg[MPS/2-1]=plist[MPS-1]-plist[MPS-2];
    
38.   maxslop[MPS/2-1]=MPS/2-1;
    
39.   for(i=MPS/2-2;i>=0;i--){
    
40.     sumf[i]=plist[2*i]+plist[2*i+1];
    
41.     sumg[i]=plist[2*i+1]-plist[2*i];
    
42.     if(sumg[i]*sumf[maxslop[i+1]]>sumg[maxslop[i+1]]*sumf[i]){
    
43.       maxslop[i]=i;
    
44.     }else{
    
45.       maxslop[i]=maxslop[i+1];
    
46.     }
    
47.   }
    
48. }
    
49. 
    
50. int main()
    
51. {
    
52.   int i,j;
    
53.   long tsum=0;
    
54.   long bx=0,by=0;
    
55.   initp();
    
56.   for(i=0;i<MPS/2-1;i++){
    
57.     long fx=sumf[i+1];
    
58.     long fy=sumg[i+1];
    
59.     bx=fx;by=fy;
    
60.     long cc=1;
    
61.     for(j=i+2;j<MPS/2;j++){
    
62.       if(by*sumf[maxslop[j]]>=bx*sumg[maxslop[j]])break;
    
63.       fx+=sumf[j];
    
64.       fy+=sumg[j];
    
65.       if(fx*by<bx*fy){//higher than best
    
66.           cc++;
    
67.           by=fy;bx=fx;
    
68.       }
    
69.     }
    
70.     tsum+=cc;
    
71.   }
    
72.   printf("%ld\n",tsum);
    
73.   return 0;
    
74. }
    

复制代码