在 c 中的长乘法期间跟踪第一个数字

Question

我有一个整数元素范围最大为10^5的数组，我必须找到总乘后的第一个元素。

示例：

Array : 2,4,6,7 
multiplication result: 336 and the first element is 3.

显然我不能乘以最大范围为 10^5 的元素。

如何在乘法过程中只跟踪第一个数字？

Answer 1

请不要忘记，这只是为了让您理解逻辑，您需要根据自己的需要对代码进行更改。我强烈建议您将其作为您程序中的子例程 并从您程序的主线程中解析给它的参数。

#include <stdio.h>
void main()
{
  int num1, num2;
  printf("Enter ur lovely number:\n");
  scanf("%d",&num1);
  num2=num1;
 while(num2)
 {
  num2=num2/10;
  if(num2!=0)
 num1=num2; 
 }
 printf("The first digit of the lovely number is %d !! :P\n ",num1);
}

Answer 2

在c或c++中将整数数据类型设为long double，这样数字的第一位在小数点之前，其余数字在小数点之后。

以上可以做如下：-

long double GetFraction(int number){
    int length = (int) log(number) + 1; // this will give number of digits in given number. And log is log base 10.
    long double fraction = (long double) number / (10^(length - 1);
    return fraction;
}

示例：-

让number = 12345

length = log(12345) + 1 = 5;
fraction = (long double) 12345 / (10^4) = 1.2345

现在为数组中的所有整数找到上面提到的分数并将它们相乘如下：-

int GetFirstDigit(int arr[] , int size){
    if(size == 0)
        return 0;
    long double firstDigit = 1.0;
    for(int i = 0 ; i < size ; i++){
        firstDigit = firstDigit*GetFraction(arr[i]);
        if(firstDigit >= 10.00) // You have to shorten your number otherwise it will same as large multiplication and will overflow.
            firstDigit/=10;
    }
    return (int) firstDigit;
}

免责声明：- 这是我的方法，我没有关于结果准确性的任何正式证据。但是我已经验证了整数最大 10^9 和数组大小最大 10^5

的结果

Answer 3

我们也可以用另一种方法找到第一个数字。

设p为所有元素相乘后的最终值

所以，我们必须找到

P = a[0]*a[1]*a[2]*a[3]*.......*a[n-1]

对于 n 大小的数组，然后我们可以在两侧取以 10 为底的对数，然后我们的表达式变为

log(p) = log(a[i])+log(a[1])+log(a[2])+.....+log(a[n-1])

现在，要找到第一个数字，我们必须得到这个变量总和的小数部分，这可以通过这种方式完成

frac = sum - (integer)sum

并在最后一步计算 10^frac 并将其转换为我们需要的第一个数字的整数值。

与时间复杂度相比，该算法更好。

int getFirstDigit(long a[], long n) {
      double p;

      for(int i=0;i<n;i++) {
           p = p+log10(a[i]);
      }

      double frac = p - (long)p;

      int firdig = (int)pow(10,frac);

      return firdig; 
}

Answer 4

试试这个方法，

将整数作为输入让我们说 int x1，现在将其复制为双数让我们说 double x2，并假设您之前的乘积为 double y，最初 y = 1。现在使用这个循环，

while(x1!<10){
    x1 = x1/10;
    x2 = x2/10; //this will make double in standard form x*10^y without 10^y part
}

ex x1 = 52，则x2将转换为5.2。现在让我们假设 y = 3 且 x 为 5.2。然后产品现在是 15.6，再次将其减少到 1.56 并重复该过程。最后你将得到小数点前唯一的数字作为所有数字乘积的第一位。

在 c 中的长乘法期间跟踪第一个数字

Track first digit during a long multiplication in c

c

arrays

algorithm

multiplication

number-systems