c - cで長い乗算中に最初の桁を追跡する

Question

までの整数要素範囲の配列があり10^5、総乗算後の最初の要素を見つける必要があります。

例：

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

明らかに、10 ^ 5 までの範囲で要素を乗算することはできません。

乗算中に最初の桁だけを追跡するにはどうすればよいですか?

Answer 1

別の方法で最初の桁を見つけることもできます。

すべての要素を乗算した後の最終値を 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 = 合計 - (整数) 合計

最後のステップで 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 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

これは単にロジックを理解してもらうための試みであり、必要に応じてコードを変更する必要があることに注意してください。これをプログラム内のサブルーチンにして、プログラム内のメイン スレッドからその引数を解析することを強くお勧めします。

#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 4

このアプローチを試して、

入力として整数を取り、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 に減らしてプロセスを繰り返します。最終的に、すべての数値の積の最初の桁として、小数点の前の唯一の桁が得られます。