ZJU_BASIC LEVEL_1017 大数相除 递归的简单应用
发布时间:2020-12-14 03:43:19 所属栏目:大数据 来源:网络整理
导读:1017. A除以B (20) 时间限制 100 ms 内存限制 32000 kB 代码长度限制 8000 B 判题程序 Standard 作者 CHEN,Yue 本题要求计算A/B,其中A是不超过1000位的正整数,B是1位正整数。你需要输出商数Q和余数R,使得A = B * Q + R成立。 输入格式: 输入在1行中依次
1017. A除以B (20)
时间限制
100 ms
内存限制
32000 kB
代码长度限制
8000 B
判题程序
Standard
作者
CHEN,Yue
本题要求计算A/B,其中A是不超过1000位的正整数,B是1位正整数。你需要输出商数Q和余数R,使得A = B * Q + R成立。 输入格式: 输入在1行中依次给出A和B,中间以1空格分隔。 输出格式: 在1行中依次输出Q和R,中间以1空格分隔。 输入样例:123456789050987654321 7输出样例: 17636684150141093474 3 /**********************************************8 @ author : GaominQuan @ Data : 2014-2-21 @ Mail : ensoleilly@gmail.com *******************************************/ #include<iostream> #include<cmath> #include<vector> #include<string> using namespace std; vector<int> answers; int R = 0; vector<int> changeToNum(string stringNum){ vector<int> numbers; for(int i = 0; i<stringNum.size(); i++){ int temp = stringNum[i] - '0'; numbers.push_back(temp); } return numbers; } vector<int> getNewNum(vector<int> numbers,int index,int remain){ vector<int> newVec; newVec.push_back(remain); /////////////////////////////////////// for(int i = index; i<numbers.size(); i++){ newVec.push_back(numbers[i]); //////////////////////////// } return newVec; } void getLongDiv(vector<int> &numbers,int b){ if(numbers.size() <= 1){ R = numbers[0]; return; }else{ int headNum = 0; /// 123455677 "123.."is head number int firstA = 0; int remain = 0; //headNum = numbers[0]; for(int i = 0; i<numbers.size(); i++){ headNum += numbers[i]; if(headNum < b){ headNum *= 10; if(i>0){ answers.push_back(0); } continue; // firstA = 0; // answers.push_back(firstA); }else{ firstA = headNum/b; remain = headNum%b; answers.push_back(firstA); /* if(remain == 0){ while(numbers[i+1] == 0){ answers.push_back(0); i++; } } */ vector<int> newNum = getNewNum(numbers,i+1,remain); numbers.clear(); getLongDiv(newNum,b); break; } } } } void div(vector<int> num,int b){ if(num.size() == 1){ cout<<num[0]/b<<" "<<num[0]%b<<endl; }else{ getLongDiv(num,b); for(int i = 0; i<answers.size(); i++){ cout<<answers[i]; } cout<<" "<<R;; } } int main(){ string input = "7"; int b = 7; cin>>input>>b; vector<int> numbers = changeToNum(input); div(numbers,b); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |