函数习题1.8 二分查找

Position BinarySearch( List L, ElementType X ){Position l=1,r=L->Last;while(l<r){Position mid=(r+l)/2;if(X>L->Data[mid]){l=mid+1;   }else if(X<L->Data[mid]){r=mid;}else{return mid;}}if(X==L->Data[l])return l;elsereturn NotFound;}

实例1.1 最大子列和问题`

#include<bits/stdc++.h>
using namespace std;
int q[1000001];
int main(){int n;cin>>n;int res=maxn=0;for(int i=1;i<=n;i++){cin>>q[i]; res+=q[i];if(res<0)res=0;        // maxn=max(maxn,res);}cout<<maxn;}

习题2.1 简单计算器

#include<bits/stdc++.h>
using namespace std;
int main(){int a,b;char c;cin>>a;while(cin>>c,c!='='){cin>>b;if(c=='+'){a=a+b;}else if(c=='-'){a=a-b;}else if(c=='*'){a=a*b;}  else if(c=='/'){if(b==0){cout<<"ERROR";return 0;}a=a/b;}else{cout<<"ERROR";return 0;}}cout<<a;}

习题2.2 数组循环左移

#include<bits/stdc++.h>
using namespace std;
int a[1001];
int n,m;
int main(){cin>>n>>m;m=m%n;for(int i=0;i<n;i++){if(i-m<0)cin>>a[i-m+n];elsecin>>a[i-m];}for(int i=0;i<n;i++){cout<<a[i];if(i!=n-1){cout<<" ";}}}

习题2.3 数列求和-加强版

a,n=map(int,input().split())
if n==0:print(0)
else:ans=(10*a*(10**n-1)//9-a*n)//9print(int(ans))

习题2.8 输出全排列

#include<stdio.h>
bool st[1000]={0};
int path[100];
void dfs(int u,int n){if(u==n+1) {for(int i=1;i<=n;i++)printf("%d",path[i]);printf("\n");return ; 
}for(int i=1;i<=n;i++){if(!st[i]){
//             printf("%d",i);st[i]=1;path[u]=i;dfs(u+1,n);st[i]=0;}}}
int main(){int n;scanf("%d",&n);dfs(1,n);
}

习题3.4 最长连续递增子序列

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[1000101];int main(){int n;int res=0,cnt=0,ans=0;int l=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){res=cnt=0;for(int j=i+1;j<=n;j++){if(a[j]>a[j-1]){cnt++;res=max(res,cnt);}else{break;}}if(res>ans){ans=res;l=i;}}if(ans==0){            //全逆序printf("%d",a[1]); return 0;}if(n==0){              // 数组个数为0return 0;}printf("%d",a[l]);for(int i=l+1;i<=l+ans;i++){printf(" %d",a[i]);}
}

习题3.9 堆栈操作合法性

#include<bits/stdc++.h>
using namespace std;int main(){int n,m;string s;cin>>n>>m;getline(cin,s);        //吸收回车键for(int i=0;i<n;i++){int res=0;bool flag=0;getline(cin,s);for(auto c:s){if(c=='S'){res++;if(res>m){flag=1;cout<<"NO"<<endl;break;}}else{res--;if(res<0){flag=1;cout<<"NO"<<endl;break;}}}if(!flag){              //没有出现非法操作if(res==0){  cout<<"YES"<<endl;}else{cout<<"NO"<<endl;         // 堆栈不是空}}}}

习题3.6 一元多项式的乘法与加法运算

#include<bits/stdc++.h>
using namespace std;
map<int,int> mp1,mp2,mp3;
int main(){int n,m;cin>>n;bool flag=0;     //判断是否为0项式for(int i=1;i<=n;i++){int a,b;cin>>a>>b;mp1[b]+=a;mp2[b]+=a;}cin>>m;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;for(auto it:mp1){mp3[it.first+b]+=a*it.second;}mp2[b]+=a;if(mp2[b]!=0){flag=1;}}if(n==0 ||m==0){cout<<"0 0";}else{for(auto it=mp3.rbegin();it!=mp3.rend();it++){if(it==mp3.rbegin()){if(it->second!=0)cout<<it->second<<" "<<it->first;}else{if(it->second!=0)cout<<" "<<it->second<<" "<<it->first;}}}cout<<endl;if(flag==0){cout<<"0 0";return 0;}for(auto it=mp2.rbegin();it!=mp2.rend();it++){if(it==mp2.rbegin()){if(it->second!=0 || it->first!=0)cout<<it->second<<" "<<it->first;}else{if(it->second!=0 || it->first!=0)cout<<" "<<it->second<<" "<<it->first;}}
//     cout<<endl;
//     for(auto it :mp2){
//         cout<<it.second<<" "<<it.first;
//     }}

习题3.10 汉诺塔的非递归实现 (25 分)

#include<bits/stdc++.h>
using namespace std;
void dfs(int n,char a,char b,char c){if(n==0)return ;dfs(n-1,a,c,b);printf("%c -> %c\n",a,c);dfs(n-1,b,a,c);}int main(){int n;cin>>n;char a='a',b='b',c='c';dfs(n,a,b,c);}

练习4.1 根据后序和中序遍历输出先序遍历

#include<bits/stdc++.h>
using namespace std;
void dfs(int post[],int ino[],int n){if(n==0){return ;}int root =post[n-1];int i;for(i=0;i<n;i++){if(root == ino[i]){break;}}cout<<" "<<root;dfs(post,ino,i);dfs(post+i,ino+i+1,n-i-1);}
int main(){int post[100],ino[100];int n;cin >> n;for (int i = 0; i <n; i++){cin >> post[i]; //确定根节点}for (int i = 0; i <n; i++){cin >> ino[i]; //确定左右}cout << "Preorder:";dfs(post,ino,n);}