以N为基数划分

Question

我想知道在C中是否有特定的算法来做到这一点。然而，我想出了一些方法。

问题是：我有两个7进制的数字。这些数字是可以整除的，所以我的答案总是整数。我想计算一下商。

最简单的方法可能是将以10为底的两个数字从以7为底转换为以10为底的两个数字，然后使用/运算符进行正常除法，然后将答案重新转换回以7为底。

这种方法有很多缺点，时间消耗过多，主要是溢出。如果divident的长度超过大约（17-19），则转换为基数10时的数字将不适合长整型。

在看了很多之后，一个简单的方法是重复乘法。示例202和13我可以在7的基数上重复添加13，直到必须添加多次才能得到202。这就是答案。然而，我无法思考如何将它们相乘。

我在寻求什么帮助？：一种算法/伪代码或代码（C/C，因为这是我唯一知道的语言），用于除以两个数，并获得以7为底的商。结果将是一个完美的整数。

#define max 2000

long long int bconvert(long long int x) //conversion from base 7 to decimal
{   long long int i=0,ans=0;
    while(x>0)
    {
    ans+=(x%10)*pow(7,i);
    x/=10;
    i++;
}
return ans;
}

 int main() {
long long int A,B,L,a,b,c,C,arr[max],i,j,k,arr1[max],r;
    scanf("%lld %lld %lld",&A,&B)
    a=bconvert(A);
    b=bconvert(B);
    c=a/b; //decimal division
    k=0;
    C=0;
    while(c>0)
    {
        r=c%7;
        c/=7;
        C+=r*pow(10,k);
        k++;
    }
    cout<<C<<endl;

输出是以7为基数的商，形式与输入相同。

Answer 1

我在寻求什么帮助？：一种算法/伪代码或代码（C/C，因为这是我唯一知道的语言），用于除以两个数字，并以7为基数获得商。

将基数7中的数字理解为基数10中的数字，这是一种曲折的过程。相反，根据输入和输出的真实基数转换数字；那就直截了当了。

#include <stdio.h>
#include <stdlib.h>

long long scanbase7()
{
    char str[24];
    return scanf("%23s", str) > 0 ? strtoll(str, NULL, 7) : -1;
}

void printbase7(long long n)
{
    long long p = 1;
    while (n/p > 7) p *= 7;
    do putchar('0'+n/p), n %= p; while (p /= 7);
    puts("");
}

int main()
{
    long long a, b, c;
    a = scanbase7();
    b = scanbase7();
    c = a/b;
    printbase7(c);
}

Answer 2

抱歉，没有时间发布完整的代码（今天晚些时候会做很多），但以下至少是“字符串”划分的一个很好的大纲。

#include <stdlib.h>
#include <string.h>

// Assume no illegal characters
char *strdivide(char *quotient, const char *dividend, const char *divisor, 
    unsigned base) {
  // consume leading zeros
  while (*dividend == '0' && dividend[1]) dividend++;
  while (*divisor == '0' && divisor[1]) divisor++;
  // Detect /0
  if (strcmp(divisor, "0")==0) {
    return "Division by 0";
  }
  // Detect dividend obviousl smaller than divisor
  size_t dd_size = strlen(dividend);
  size_t dv_size = strlen(divisor);
  if (dd_size < dv_size) {
    return strcpy(quotient, "0");
  }

  // Work with copy of dividend
  char div[dd_size + 1];
  memcpy(div, dividend, dd_size + 1);

  // Form quotient
  size_t places = dd_size - dv_size;
  for (size_t i = 0; i<=places; i++) {
    // Assume ASCII
    int digit = 0;
    while (strcmp(div, divisor) >= 0)) {
      int borrow = 0;
      for (unsigned j = dv_size; j-- > 0; ) {
        int diff = value(div[j]) - value(divisor[j]) - borrow;
        if (diff < 0) {
          diff += base;
          borrow = 1;
        } else {
          borrow = 0;
        }
        div[j] = unvalue(diff);
      }
    }
    quotient[i] = unvlaue(digit); // int to char
  }
  quotient[i] = '\0';
  // Check for leading 0 in `quotient[]`, shift if needed.
  return quotient;
}

Answer 3

您可以直接在输入字符串上实现长除法算法。

另一种选择是将数字转换为以16807为基数（7**5）的任意精度整数，在该基数中进行除法，然后将结果转换回以7为基数。