Skip to content

11631: 【原1631】字符串相除

题目

题目描述

author: jankyee 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1631

Description

给定两个字符串(str1和str2),求它们相除的“商”。

Example:

给定字符串

  • str1=“1005”
  • str2=“89”

str1除以str2的商是“15”,详细过程是:将两个字符串分别"看做"整型数5001和98, 整型数5001除以整型数98的商是51,最后再反转,得出的结果即是”15“

再如

  • str1=“9876”
  • str2=“3”

输出结果是“3622”

Note:

  • 字符串中的所有字符均在‘0’-‘9’之间
  • 无需考虑空字符串或者“0”字符串的情况
  • ”商“仍为字符串(注意不能是数字)
  • 输入有一行:分别是str1和str2,中间用空格隔开;输出一行:字符串的“商”
  • 对于所有测试用例,字符串最大长度小于501
  • 本次上机不再限定指针,可以使用string类或者其他方法,实现结果即可。

Sample Input

1005 89

Sample Output

15

Pangbo13's solution

#include<iostream>
#include<cstring>
using namespace std;
char str1[501],str2[501],ans[501];
bool compare(char* s1,char* s2,int l1,int l2){//s1更大或等于则返回true
    int i1,i2;
    for(int i = 1; i <= l2 ; i++){
        if(str1[l1-i]<str2[l2-i]) return false;
        else if(str1[l1-i]>str2[l2-i]) return true;
    }
    return true;
}
void sub(char* s1,char* s2,int l1,int l2){
    int i1,i2;
    for(int i = 1; i <= l2 ; i++){
        str1[l1-i] -= (str2[l2-i]-'0');
        for(int j=0;str1[l1-i+j]<'0';j++){
            str1[l1-i+j] += 10;
            str1[l1-i+j+1] -= 1;
        }
    }
}
int main(){
    int len1,len2,lenans,ansp;
    cin>>str1>>str2;
    len1 = strlen(str1);
    len2 = strlen(str2);
    ans[0] = '0';
    lenans = compare(str1,str2,len1,len2)?len1-len2+1:len1-len2;
    ansp = lenans-1;
    for(;ansp>=0;ansp--){
        ans[ansp] = '0';
        while(ansp+len2<len1){
            sub(str1,str2,ansp+len2,len2);
            ans[ansp]++;
            if(str1[len1-1] == '0') {
                str1[len1-1] = 0;
                len1--;
                }
        }
        while(compare(str1,str2,len1,len2)){
            sub(str1,str2,len1,len2);
            ans[ansp]++;
        }
        if(str1[len1-1] == '0') {
            str1[len1-1] = 0;
            len1--;
            }
    }
    cout<<ans;
}