多内容会在godownio.github.io更新
算法练习(C++代码)
考研上机或C语言代码笔试准备,暨大机试原题+letcode+牛客+中南大等高校机试
快速幂算法
题目:输入一个整数 n ,求 n^n 的个位数是多少。
快速幂算法:指数为偶数,则底数平方,指数除二;指数为奇数,则指数减一再把结果乘底数,底数平方,指数除二。指数看作二进制,除二可以看作位运算。
#include using namespace std; int main(){ int n; cin>>n; int power=n; int base=n; int result = 1; while(power>0){ if(power%2==1){ result *= base; power /= 2; base *= base;//指数为奇数,先乘底数。除二小数部分舍去。底数平方 } else{ power /= 2; base *= base;//指数为偶数,除二,底数平方 } } cout if(n==1||n==2){ return 1; } else return f(n-2)+f(n-1); } int main(){ int n; cin n; cout int n,m; cout cinscore[i]; } //cout for(int j=n-i-1;j0;j--){ if(score[j]score[j-1]){ int temp = score[j]; score[j] = score[j-1]; score[j-1] = temp; } }//冒泡排序 } int i=0,j; for(j=1;j if(score[j]!=score[i]){ score[++i]=score[j]; } }//双指针去重 cout cout cout stack if(strs[i]=='('||strs[i]=='{'||strs[i]=='['){ s.push(strs[i]); } if(strs[i]==')'){ if(!s.empty()&&s.top()=='(') s.pop(); else{ cout if(!s.empty()&&s.top()=='{') s.pop(); else{ cout if(!s.empty()&&s.top()=='[') s.pop(); else{ cout if(m1&&n1){ return path(m-1,n)+path(m,n-1); }else return 1;//1*2或者2*1或者1*6的路径选择都为1个 } int main(){ int m,n; cinmn; cout int dp[m][n]; for(int i=0;i for(int j=0;j if(j0&&i0){ dp[i][j]=dp[i-1][j]+dp[i][j-1]; } else{ dp[i][j]=1; } } } return dp[m-1][n-1]; } int main(){ int m,n; cinmn; cout{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}; // 将数组转换为 std::vector vector matrix.push_back(vector int m=block.size(),n=block[0].size(); vector for(int j=0;j if(block[i][j]==0){ if(j0&&i0){ dp[i][j]=dp[i-1][j]+dp[i][j-1]; }else{ dp[i][j]=1;//第一行或第一列 } }else{ dp[i][j]=0;//有障碍物 } } } return dp[m-1][n-1]; } int main(){ int rows,cols; cout for(int j=0;j cinblock[i][j]; } } cout if(nm) return m; else return n; } int path(vector int m=block.size(),n=block[0].size(); vector for(int j=0;j if(i0&&j==0){ dp[i][j]=dp[i-1][j]+block[i][j];//第一行 } if(j0&&i==0){ dp[i][j]=dp[i][j-1]+block[i][j];//第一列 } if(j0&&i0){ dp[i][j]=min(dp[i][j-1],dp[i-1][j])+block[i][j]; } } } return dp[m-1][n-1]; } int main(){ int rows,cols; cout for(int j=0;j cinblock[i][j]; } } cout int lowcost = 0; for(int i=0;i if(T T = lowcost + (T-lowcost)*H[i]; return T; }//菜品总价小于折扣 else{ lowcost = lowcost + z[i]*H[i];//lowcost为当前折扣限度,比如第二轮中就是0.6*100+0.8*200 cout int N,T; cout //cout for (int j=i;j if(z[j]z[i]){ double tempz;int tempH; tempz=z[j];z[j]=z[i];z[i]=tempz; tempH=H[j];H[j]=H[i];H[i]=tempH; } }//折扣排序 } int cost = paychase(N,T,z,H); cout