2

我有一个整数元素数组，范围高达10^5，我必须在总乘法之后找到第一个元素。

例子：

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

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

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

4

4 回答 4

4

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

假设 p 是所有元素相乘后的最终值。

所以，我们必须找到

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

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

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; 
}
于 2016-06-16T04:12:51.523 回答
1

输入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

于 2016-06-10T04:10:58.133 回答
0

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

#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);
}
于 2016-06-09T10:20:54.597 回答
0

试试这个方法，

将整数作为输入让我们说 int x1，现在将其复制到 double 中，让我们说 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 并重复该过程。最后，您将拥有小数点前的唯一数字作为所有数字乘积的第一位。

于 2016-11-06T20:51:56.407 回答