当前位置:编程问答 > C/C++ >

C++大数问题

问题:怎样存一个输入的大数,例如10^100
然后再把这个数开平方.
具体怎么实现,请指教.
答案:可以当作字符串来处理。
你可以试着用二分法尝试一下,具体我没做过。

先写一个大数乘法函数,输入输出全是字符串。
然后,用二分法。比如求50000的开平方,
先试5000/2=2500,2500*2500>5000,于是
试  2500/2=1250, 1250*1250>5000, 于是
试  1250/2=625,  ……
……
试  156/2=78,  78*78>5000, 于是
试  78/2=39,   39*39<5000, 于是可以定位在39-78之间,
试(39+78)/2=57, 57*57<5000, 于是可以定位在57-78之间,
试 (57+78)/2=67,67*67<5000,于是可以定位在67-78之间,
试  (67+78)/2=72, 72*72>5000, 于是可以定位在67-72之间
……
最后定位在70-71之间,至于取哪个,看你怎么选了。


这是我写的一个求阶乘的函数,不知道对你有没有帮助。


#include <stdio.h>
#include <math.h>

#define  LEN  1000

void  multi_string(char *data_s1, char *data_s2, char *data_product);
void  multi_string_single(char *data_s, char ch, char *data_sum);
void  add_string(char *data_s1, char *data_s2, char *data_sum, int len_sum);
int   ctoi(char ch);
char  itoc(int data);
void  shift_left(char *data, int num);
void  factorial(int  order, char *pro_result);



/*=========================================================================*/

int  ctoi(char ch)
{
  switch(ch)
  {
    case '0'  :  return 0;
    case '1'  :  return 1;
    case '2'  :  return 2;
    case '3'  :  return 3;
    case '4'  :  return 4;
    case '5'  :  return 5;
    case '6'  :  return 6;
    case '7'  :  return 7;
    case '8'  :  return 8;
    case '9'  :  return 9;
    default   :  return 0;
  }

}

char  itoc(int data)
{
     switch(data)
    {
      case 0  :  return '0';
      case 1  :  return '1';
      case 2  :  return '2';
      case 3  :  return '3';
      case 4  :  return '4';
      case 5  :  return '5';
      case 6  :  return '6';
      case 7  :  return '7';
      case 8  :  return '8';
      case 9  :  return '9';
      default   :  return '0';
    }
}



/*=========================================================================*/

void  multi_string_single(char *data_s, char ch, char *data_pro)
{
  int times;
  int i,j,k;
  int len, len_0;
  int len_pro_0;
  int sum_tmp;
  int carry;
  int add_bits;


  len = 0;
  len_0 =0;
  len_pro_0 = 0;

  times = ctoi(ch);
 
  while(data_s[len_0]=='0')   {  len_0++;}
  while(data_pro[len_pro_0]=='0') {  len_pro_0++;}

  while(data_s[len]!='\0')   {  len++;  }


  for(i=0;i<LEN;i++)  {  data_pro[i] = '0';  }


  /* begin to add*/
  carry = 0;
  sum_tmp = 0;
  add_bits = 0;
  for(k=0;k<times;k++)
  {
    carry = 0;
    for(i=0;i<len - len_0 + add_bits;i++)
    {
       sum_tmp = ctoi(data_pro[LEN-1-i]) + ctoi(data_s[len-1-i]) + carry;
       /* printf("\n%d = %d + %d + %d ; add_bits=%d\n" , sum_tmp, ctoi(data_pro[LEN-1-i]), ctoi(data_s[len-1-i]), carry , add_bits);}*/

       data_pro[LEN-1-i] = itoc( sum_tmp % 10 );
       carry = sum_tmp/10;
    }

    if(carry==1)  {  add_bits++;  data_pro[LEN-1-i] = itoc(carry);  }

  }

  /* end adding */

  return;
}



/*=========================================================================*/

void  add_string(char *data_s1, char *data_s2, char *data_sum, int len_sum)
{

   int i,j,k;
   int carry;
   int sum_tmp;
   int len1,len2;
   char  data_s1_bit;
   char  data_s2_bit;

   len1=0;
   len2=0;

   while(data_s1[len1]!='\0') {len1++;}
   while(data_s2[len2]!='\0') {len2++;}

   carry = 0;
   for(i=0;i<len_sum;i++)
    {
       if(i>=len1)  {  data_s1_bit = '0';  }  else {  data_s1_bit = data_s1[len1-1-i];  }
       if(i>=len2)  {  data_s2_bit = '0';  }  else {  data_s2_bit = data_s2[len2-1-i];  }

       sum_tmp = ctoi(data_s1_bit) + ctoi(data_s2_bit) + carry;
       data_sum[len_sum-1-i] = itoc( sum_tmp % 10 );
       carry = sum_tmp/10;
    }

    return;
}



/*=========================================================================*/

void  shift_left(char *data, int num)
{
   int i;
   int len;

   len=0;
   while(data[len]!='\0') {len++;}

   for(i=0;i<len;i++)
   {
      if(i<len-num)  {  data[i] = data[i+num];  }
      else           {  data[i] = '0';          }
   }

   return;
}



/*=========================================================================*/

void  multi_string(char *data_s1, char *data_s2, char *data_product)
{
  char data_pro_tmp[LEN+1];
  char data_pro_single_tmp[LEN+1];
  unsigned int len1_0, len2_0;
  unsigned int len1,  len2;
  unsigned int len_pro;
  int i,j,k;

  len1_0 = 0;
  len2_0 = 0;
  len1 = 0;
  len2 = 0;
 
  while(data_s1[len1_0]=='0') {  len1_0++;  }
  while(data_s2[len2_0]=='0') {  len2_0++;  }

  while(data_s1[len1]!='\0') {  len1++;  }
  while(data_s2[len2]!='\0') {  len2++;  }

  for(i=0;i<LEN;i++)
  {
    data_pro_tmp[i] = '0';
    data_pro_single_tmp[i] = '0';
  }
    data_pro_tmp[i] = '\0';
    data_pro_single_tmp[i] = '\0';


  for(k=0;k<len2-len2_0;k++)
  {
    multi_string_single(data_s1, data_s2[len2-1-k], data_pro_single_tmp);

    shift_left(data_pro_single_tmp, k);
    add_string(data_pro_single_tmp, data_pro_tmp, data_pro_tmp, LEN);
  }

  for(i=0;i<LEN;i++)  {  data_product[i] = data_pro_tmp[i];  }

  return;
}



/*=========================================================================*/

void  factorial(int  order, char *pro_result)
{
   int i,j;
   char  added_number[LEN+1];

   pro_result[LEN] = '\0';
   added_number[LEN] = '\0';

   /* initial added_number */
   for(i=0;i<LEN-1;i++)  {  added_number[i] = '0';  pro_result[i] = '0';  }
   added_number[LEN-1] = '1';
   pro_result[i] = '1';

   for(j=0;j<order;j++)
   {
     multi_string(added_number, pro_result, pro_result);
     add_string(added_number, "1", added_number, LEN);
   }

   return;
}

main()
{
   char  pro_result[LEN+1];
   char  added_number[LEN+1];
   int len;
   int i,j,k;
   int order;
   char judge;


   /* char  s1[LEN+1] = "0000011199"; */
   /* char  s2[LEN+1] = "0000022299"; */

    char  s1[LEN+1] = "123456";
    char  s2[LEN+1] = "123456";
    char  s3[LEN+1];
    char  s4[LEN+1];


   s1[LEN] = '\0';
   s2[LEN] = '\0';
   s3[LEN] = '\0';
   s4[LEN] = '\0';
   pro_result[LEN] = '\0';
   added_number[LEN] = '\0';

   /* multi_string(s1, s2, s3);  printf("\n%s * %s = %s\n", s1, s2, s3); */

   /* multi_string_single(s2, '9', s_pro); */
   /* printf("\ns_pro = %s\n", s_pro); */

   /* initial added_number */

   order = 1;
   judge = '';



   while(1)
   {
     printf("\n\n###########################################\n");
     printf("\nPlease input the factorial number (between 1 and 400):  ");
     scanf("%d",&order);

     if(order>=0 && order <=400)
     {
      factorial(order,s4);


      printf("\n%d! = ", order);
      k=0;
      while(s4[k]=='0')  {  k++; }
      while(s4[k]!='\0') {  printf("%c",s4[k]);  k++;  }
      printf("\n\n");

      /*printf("\n%d! = %s\n\n", order, s4); */

     }
     else
       {
          printf("\nPlease input the correct number (between 1 and 100)!\n\n");
       }

     printf("Press  q  to exit, Press  c  to continue:  ");
     scanf("%s",&judge);
     if(judge=='q'||judge=='Q')  {  break;  }

   }

    if(judge!='q' && judge!='Q')
    {  printf("\n\nPress Enter to exit.\n");
       getch();
    }

}

用数组存储  再写个开方的函数

大数的话用字符串接受输入,而后再通过减字符a来转换成数字,至于平方嘛,好像是要错位乘吧,呵呵,

上一个:C++ 编程 计算机
下一个:c++编程题

CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,