【OJ基础练习大全】大数问题+循环数组

Myth丶恋晨 2022-11-12 14:58 169阅读 0赞

**一、整理题目**

***大数问题***

1.  大数相加
2.  大数相减
3.  再分麦粒

***循环数组模拟***

1.  狱史问题
2.  玛雅日历
3.  All in All

**二、解题思路**

大数问题：  
（1）根据题目描述进行开始char\[\]数组或者string的声明（使用数组进行long long（一般计算机64位，也就是最长类型只能2的64次方的范围）都无法进行存储的数据存储）。  
（2）进行char与int的转换（char 对应ascii码，char-'0’即为int的数字）。  
常见编码：ascii,UTF-8,GB2312。  
（3）运输处理（若加法，先进行全部相加，最后考虑进位问题）  
（4）逆置输出，考虑低位和高位问题

大数相减代码（加法类似）：

#include "iostream"
    #include "algorithm"
    #include <string.h>
    using namespace std;
    
    // string和char[]? 
    
    char a[201],b[201];
    
    void reserve(char* arr,int n){  //数组传入指针即可改变值返回？？ 
    	for(int i =0;i<n/2;i++){ 
    		swap(arr[i],arr[n-i-1]);
    	}
    }
    
    void handle(){ 
    
    	   int lena =strlen(a),lenb=strlen(b);
    	   
    	   reserve(a,lena);
    	   reserve(b,lenb); // 改成低位开始计数
    	   
    	   int intA[lena],intB[lenb],intC[201];//声明int型
    	   int maxL = lena>lenb?lena:lenb;
    	   
    	   for(int i =0;i<maxL;i++){ 
    	   	    
    	   	    if(i<lena&&i<lenb){ 
    	   	    		    intA[i]=a[i]-'0';
    	   	    			intB[i]=b[i]-'0';
    	   	    			intC[i]=intA[i]-intB[i];
    			   }
    			   
    			else    if(i<lena){ 
    	   	    	intC[i]=a[i]-'0';
    			   }
    // else if(i<lenb){ 
    // intC[i]=b[i]-'0';
    // } 
    	   } 
    
    	   for(int i=0;i<maxL;i++){ 
    	   	 if(intC[i]<0){ 
    			 intC[i+1]-=1;
    			 intC[i]+=10;
    		 } 
    	   }
    	   if(intC[maxL-1]==0){ 
    	   	 for(int i=maxL-2;i>=0;i--){ 
    	   	 	cout<<intC[i];
    		}
    	   }else{ 
    	   		 for(int i=maxL-1;i>=0;i--){ 
    	   	 	cout<<intC[i];
    		}
    	   }
    	   
    }
    
    int main(){ 
    	
        while(cin>>a>>b){ 
     	       handle();
     	       cout<<endl;
    	}
    
    	return 0;
    	
    }```
    
    
    再分麦粒(注意2的n次方求和公式）:
    
    ```c
    #include "iostream"
    #include "time.h"
    //
    //#include <stdafx>
    //#include <windows.h>
    
    using namespace std;
    // 再分麦粒
    void handle(int n)
    { 
    	int arr[501]={ 0};
    	bool cache[501]={ false};
    	
    	arr[0] =1;// 设第一位为1
    	cache[0]=true;
    	
    // int flag = 1;
    	for(int i =1;i<n;i++){ 
    		int j=0;// j指向数组进行乘法
    		while(j<500){  //想办法进行优化？ cache[j]&&
    			arr[j]*=2;
    			j++;
    		} 
    		j = 0;
    		while(j<500){ //cache[j]&&
    			if(arr[j]>=10){ 
    				arr[j]%=10;
    				arr[j+1]+=1;
    				cache[j+1]=true;//进位说明该位置已经访问到 
    			}
    			j++;
    		}	
    	}
    		// 再进行减一操作
    		int j = 0;
    		arr[j]--;
    		while(arr[j]<0){ 
    			arr[j+1]--;
    			arr[j]=9;
    			j++;
    		}
    
    	for(int i=499;i>=0;i--)
    		cout<<arr[i];
    	cout<<endl;	
    }
    
    int main(){ 
    	int n;
        cin>>n;
        
    // 
    	long time_start, time_end;
    	
    	time_start = clock();
    // 
    // /* 获取开始时间 */
    // time_start = GetTickCount(); //从操作系统启动经过的毫秒数
    
    	handle(n+1); // 总数等于n+1项-1 
    	
    	time_end= clock();
    	
    	cout<<"时间："<<(time_end - time_start) ;
    	return 0;
    }

循环数组：

（1）日历转换类：多为三重循环，进行遍历，注意day进位，month进位条件，考虑使用取余进行循环。  
（2）模拟类：进行抽象模拟，然后循环判断、改变。

#include "iostream"
    using namespace std;
    
    // Haab: day month year (365天，18*20+5）=> Tzolkin
    // 天数字 天名称 年数
    
    // 思路：从第一天开始计数遍历到相等时则换个形式输出
    
    
    string months[19]= { "pop", "no", "zip", "zotz", "tzec", "xul", "yoxkin", "mol", "chen", "yax", "zac", "ceh", "mac", "kankin", "muan", "pax", "koyab", "cumhu","uayet"};
    
    // Tzolkin的日子对应名称 
     
    string days[20]={ "imix", "ik", "akbal", "kan", "chicchan", "cimi", "manik", "lamat", "muluk", "ok", "chuen", "eb", "ben", "ix", "mem", "cib", "caban", "eznab", "canac", "ahau"};
    
    
    // 用map 
    int getMonthInt(string month){ 
      	for(int i =0;i<19;i++){ 
      		if(month==months[i])
      		return i;
    	  }
    	  
    	return -1;//错误 
    }
    
    void handle(int day,string month,int year){ 
    	// Tzolkin
    	int day2=1,day2Name=0,year2=0;//初始化 
    	
    	for(int i=0;;i++){ // 年＋ 0年 
    	    for(int j=0;j<19;j++){  //0-18 、、getMonthInt(month) 
    	    	int max;
    	    	if(j==18){  // 若最后一个月则五天 
    	    		max = 5;
    			}else{ 
    				max = 20;
    			}
    			for(int k=0;k<max;k++){ 
    	    		if(i==year&&months[j]==month&&k==day){ //j=getMonthInt(month)
    			        cout<<day2<<" "<<days[day2Name]<<" "<<year2<<endl; 
    					return ;  
    				}  
    				day2=(day2)%13+1;//循环取余
    				day2Name=(day2Name+1)%20;
    				if(day2==1&&day2Name==0){ 
    					year2++;
    				}
    // if(day2==1){ 
    // day2Name=(day2Name+1)%13;
    // if(day2Name==0){ 
    // year2++;
    // } 
    // } 
    			}
    		} 	
    	}
    } 
    
    
    int main(){ 
    	
    	int n,day,year;
    	string month;
    	cin>>n;
    	for(int i =0;i<n;i++){ 
    		cin>>day>>month>>year;
    		handle(day,month,year);
    	}
    }

All in all

#include "iostream"
    using namespace std;
    
    
    bool handle(string s,string t){  //s子串，t主窜 
    	
    	int i=0,j=0;
    	int lenS = s.size(),lenT=t.size();
    	
    	if(lenS>lenT){ 
    		return false;
    	}
    	
    	for(;j<lenT;j++){ 
    		if(s[i]==t[j]){ 
    			i++;//移动子串 
    		}
    		if(i==lenS-1){ 
    			return true;
    		}
    	}
    	
    	return false;
    }
    
    int  main(){ 
    	string str1,str2;
    	
    	while(cin>>str1>>str2){ 
    		if(handle(str1,str2)){ 
    			cout<<"Yes"<<endl;
    		}else{ 
    			cout<<"No"<<endl;
    		}
    	}
    	
    	return 0;
    }