编程之美问题记录——数字之魅1

编程之美问题记录——数字之魅1

抽出一部分时间看了一点编程之美，思考的乐趣确实是一种享受。

求二进制中1的个数

分析：直接判断每一位，时间O(log2(n))。可以只判断”1”的个数。 810=000010002 只利用8本身来快速判断：它不是0，但是 00001000 & 00000111 = 00000000

int check(int n){ int ans=0; while(n){ ans++; n=n&(n-1); } return

N!中末尾0的个数

（十进制中末尾0个数） 分析：这个问题可以转化成有多少个2和5的配对数。因为2的个数总是大于5的个数，即问题变成求解1——n中所有因子5的个数。 如30!，即是1——30的乘积，与5相关的数字有5,10,15,20,25,30，6个数字，同时25其实贡献了2个5，所以共有7个5。30/5=6. 6/5=1

int zero(int n){ int ans=0; while(n){ ans+=n/5; n/=5; } return

求解N!二进制数字最低位1的位置。

（二进制中末尾0的个数） 分析：我们需要求出计算结果二进制形式的末尾0的个数，这和上面的问题联系在了一起，不过这次需要统计因子2的个数，有多少个2就提升多少位。但是书中给出了一种更加优秀的做法。h2的个数=N2+N4+N8+N16+⋯ 例如求解27!的二进制中最低位1的位置。

2710=110112h=1101+110+11+1=(1000+100+00+1)+(100+10+0)+(10+1)+1=(1000+100+10+1)+(100+10+1)+1=1111+111+1=(10000−1)+(1000−1)+(10−1)+(1−1)[构造]=11011−1的个数

即n!末尾0的个数就是数字本身n-二进制中1的个数。

int two_zero(int n){ int ans=0,old=n; while(n){ ans++; n=n&(n-1); } return

寻找最大的k个数

分析：可以用一个特别的数组装下最大的ｋ个数字，然后对于每一个新的数字判断它和其中最小值的关系，如果小弃之，大则替代最小值并更新这个数组。所以这个数组可以是最小堆，也可以是优先队列。

#include #include #include using namespace std;int g[1010];void adjust(int p,int k){ int q=p<<1; if(g[q]>g[q+1]) q++; if(q>k) return ; if(g[p]>g[q]){ 　int t=g[p]; g[p]=g[q]; g[q]=t;　　 adjust(q,k); }}int main(){ //freopen("cin.txt","r",stdin); int n,k; // k<1010 while(cin>>n>>k){ for(int i=1;i<=k;i++) scanf("%d",&g[i]); sort(g+1,g+1+k); for(int i=k+1;i<=n;i++){ int t; scanf("%d",&t); if(t>g[1]) { g[1]=t; adjust(1,k); } } for(int i=1;i<=k;i++){ printf("%d ",g[i]); } puts(""); } return 0;}

最大公约数问题。

求解两个数的最大公约数 分析：传统的gcd()做法是

int gcd(int a,int b){ return b==0?a:gcd(b,a%b);}

但是由于有取模的存在，有时会影响效率。 我们知道if (a,b)=c and a=p*a’, b%p!=0 then (a,b)=(a’,b)=c。　即可以取出不相关的部分。 那么，结合计算机的运算特点，可以进行左移和右移提取２。

#include #include #include using namespace std;typedef long long LL;bool odd(LL a){ return a&1LL;}LL gcd(LL a,LL b){ if(a>b) swap(a,b); if(a==1) return 1; if(a==0) return b; if(odd(a) and odd(b)) return gcd(a,b-a); if(!odd(a) and odd(b)) return gcd(a>>1,b); if(odd(a) and !odd(b)) return gcd(a,b>>1); if(!odd(a) and !odd(b)) return gcd(a>>1,b>>1)<<1;}int main(){ LL a,b; while(cin>>a>>b){ cout<

计算斐波那契第n项值

快速计算的方式有: 1. 使用通项公式。 F(n)=5√5((1+5√2)n−(1−5√2)n)

最开始的几项值先递推计算出来并保存，后面n较大的情况可以使用此公式。 但是这种方法有浮点误差。 2. 矩阵快速幂，分治策略。 我们知道

(F(n)F(n−1))=(1110)(F(n−1)F(n−2))

所以，由此可以推算第n项。

快速寻找满足条件的两个数。

能否在一个数组里寻找两个数字，使得他们的和等于一个给定的数。 分析：将数组有序排列，比如从小到大。一个指针放左边，一个指针放右边，双方不断向中间移动，如果大了右指针左移，小了左指针右移。直到找到那个数字。

struct node{ int p1, p2; node(int _p1,int _p2){ p1=_p1; p2=_p2; };};node myfind(int a[],int n,int sum){ int i=0,j=n-1; while(isum) j--; else i++; } return node(-1,-1);}

有一个此问题的拓展应用​

子数组的最大乘积。

计算长度是N的整数数组中任意N-1个数的组合中最大的一组。

分析：如果没有乘法计算溢出情况出现，可以直接先计算出所有数字的乘积然后针对第i个数字做除法分析即可。

如果存在乘法溢出的情况：

当所有数字的乘积b大于0，当前数字是a[i]–>x, 那么剩下的N-1个数字的乘积y=b/x，函数图像：

当b小于0,y=b/x函数图像：

还有b等于0的情况，如果数组中存在两个以上的0，那么y就等于0。如果仅仅存在一个0，那么我们可以统计正数和负数的个数分析得出结论。

所以，求解正数的个数，负数的个数，0的个数即可。

求解数组的子数组的最大和。

最大连续子序列问题。 分析：如果从前缀和考虑，那么时间复杂度是n^2 中间过程分析，每一个数字和前面数字的和要么相加要么不加，取最大的那种情况，不断更新答案。dp实现线性n的时间复杂度

int max_sum(int *a,int n){ int ans=a[0],temp=a[0]; for(int i=1;i

子数组的最大和 - 二维

和上面的问题类似，但是二维（注意连续）。

分析：直接枚举计数的效果不理想。因为它和上面的问题有一定的相似性，可以借鉴上面的问题的解法。可以固定上下界然后就变成了一维子数组最大和的问题了。

code:

#include #include using namespace std;int g[6][6]={1,-1,5,3,6,-2,3,-2,7,8,-3,4,4,2,1,6,-4,7,5,2,1,0,1,1,-2,5,3,1,-2,1,1,2,-1,4,3,0};int h[6][6][6]; // h[j][r1][r2]第j列row1到row2的元素的和int main(){ for(int j=0;j<6;j++){ for(int r1=0;r1<6;r1++){ for(int r2=r1;r2<6;r2++){ int temp=0; for(int r=r1;r<=r2;r++){ temp+=g[r][j]; } h[j][r1][r2]=temp; } } } int ans=-(1<<29); for(int r1=0;r1<6;r1++){ //dp for(int r2=r1;r2<6;r2++){ int temp=h[0][r1][r2]; ans=max(ans,temp); for(int j=1;j<6;j++){ temp=max(h[j][r1][r2],temp+h[j][r1][r2]); ans=max(ans,temp); } } } printf("%d\n",ans); ans=-(1<<29); for(int i1=0;i1<6;i1++){ // 暴力 for(int j1=0;j1<6;j1++){ for(int i2=i1;i2<6;i2++){ for(int j2=j1;j2<6;j2++){ int temp=0; for(int i=i1;i<=i2;i++){ for(int j=j1;j<=j2;j++){ temp+=g[i][j]; } } ans=max(ans,temp); } } } } printf("%d\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。