| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4829 人关注过本帖
标题:求助: 任意大数相加怎么做?
只看楼主 加入收藏
雪城白鸟
Rank: 1
来 自:吉林
等 级:新手上路
帖 子:22
专家分:0
注 册:2008-3-15
收藏
 问题点数:0 回复次数:13 
求助: 任意大数相加怎么做?
用数组做任意大数相加,怎么编 ?我做的错了 谢谢~~~
搜索更多相关主题的帖子: 大数 相加 
2008-03-15 19:21
浩天
Rank: 1
等 级:新手上路
帖 子:86
专家分:0
注 册:2007-11-17
收藏
得分:0 
就用下标访问相加后就是了啥
2008-03-15 20:12
雪城白鸟
Rank: 1
来 自:吉林
等 级:新手上路
帖 子:22
专家分:0
注 册:2008-3-15
收藏
得分:0 
还有疑问
但是要考虑到开始申请的数组大小以及进位,能帮忙留下代码吗?
2008-03-15 20:31
newyj
Rank: 2
等 级:新手上路
威 望:3
帖 子:542
专家分:0
注 册:2008-1-4
收藏
得分:0 
我是新手 只是说出来自己的想法
用指针方式来计算
如果是一维数组的话  NUM+=*(P+I)
如果是二维的话 NUM+=*(*(P+I)+J)
不知道 是否正确
2008-03-15 20:47
PcrazyC
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:5652
专家分:0
注 册:2006-10-20
收藏
得分:0 
学过链表没,用链表操作吧

雁无留踪之意,水无取影之心
2008-03-15 23:23
PcrazyC
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:5652
专家分:0
注 册:2006-10-20
收藏
得分:0 
头文件(DLNode.h)
程序代码:
#include<stdlib.h>

typedef int DataType;
typedef struct DoubleNode        //定义链表元素
{
    DataType data;
    struct DoubleNode *prior;
    struct DoubleNode *next;
}DLNode;

void InitNode(DLNode **head)    //初始化链表
{
    if((*head=(DLNode*)malloc(sizeof(DLNode)))==NULL)
        exit(1);
    (*head)->prior=*head;
    (*head)->next=*head;
}

int InsertNode(DLNode *head,int n,DataType x)    //向链表第N个位置插入元素X
{
    DLNode *p,*nt;
    int i=0;
    p=head->next;
    while(p!=head&&i<n)
    {
        p=p->next;
        i++;
    }
    if(i!=n)
    {
        printf("插入位置错误\n");
        return 0;
    }
    if((nt=(DLNode *)malloc(sizeof(DLNode)))==NULL)
        exit(1);
    nt->data=x;
    nt->prior=p->prior;
    nt->prior->next=nt;
    nt->next=p;
    p->prior=nt;
    return 1;
}

int digit(int n)    //判断整数N有几位
{
    int i;
    for(i=1;;n/=10,i++)
    {
        if(n/10==0)
            return i;
    }
}

void PrintNode(DLNode *head)    //打印链表
{
    DLNode *p=head->next;
    int i;
    while(p->data==0)        //去掉前面的一串0
    {
        p=p->next;
        if(p==head)
        {
            printf("0\n");
            return;
        }
    }
    printf("%d",p->data);    //最前面的一个数进行特殊处理,不用补零
    p=p->next;
    while(p!=head)            //打印后面的数字
    {
        printf(",");
        if(p->data==0)
        {
            printf("0000");
            p=p->next;
            continue;
        }
        for(i=0;i<4-digit(p->data);i++)    //补零
            printf("0");
        printf("%d",p->data);
        p=p->next;
    }
    printf("\n");
}

void DestroyNode(DLNode **head)
{
    DLNode *p,*p1;
    p=(*head)->next;
    while(p!=*head)
    {
        p1=p;
        p=p->next;
        free(p1);    
    }
    free(p);
    head=NULL;
}


CPP文件
程序代码:
/*****************************************************

  由于计算机所提供的数据类型其范围和有效数字太少,处理比较大的数时非常不精确,下面我们用
  双向链表作来处理大整数的加法,还可以用来处理乘法除法之类的,在这就不说了.

*****************************************************/
#include<stdio.h>
#include"DLNode.h"    
#include<string.h>    
#include<stdlib.h>
#include<math.h>

#define N 100

void plus(DLNode *h1,DLNode *h2)            //两数相加
{
    DLNode *p1=h1->prior,*p2=h2->prior;
    while(p1!=h1&&p2!=h2)                //每个链表元素相加
    {
        p1->data+=p2->data ;
        p1=p1->prior;
        p2=p2->prior;
    }
    p1=h1->prior;
    while(p1!=h1->next)                    //处理链表元素
    {
        if(p1->data>=10000)
        {
            p1->prior->data+=p1->data/10000;
            p1->data%=10000;
        }
        if(p1->data<0)            //处理负数
        {
            if(h1->next!=0)
            {
                p1->prior->data-=1;
                p1->data+=10000;
            }
        }
        p1=p1->prior;
    }
        
    if(h1->next->data>=10000)                //处理最前面的数
    {
        InsertNode(h1,0,h1->next->data/10000);
        h1->next->next->data%=10000;
    }
    if(h1->data<=-10000)
    {
        InsertNode(h1,0,h1->next->data/10000);
        h1->next->next->data%=-10000;
    }
    PrintNode(h1);
}

int main()                            //入口函数
{
    DLNode *head1,*head2;
    InitNode(&head1);
    InitNode(&head2);
    char data1[N],data2[N];
    char d1[10],d2[10];
    int i,j,k;
    while(scanf("%s %s",data1,data2))
    {
        InitNode(&head1);
        InitNode(&head2);
        i=0;k=0;
        while(data1[i]!=';')            //将数1用链表储存
        {
            for(j=0;j<10;j++)
                d1[j]=0;
            j=0;
            while(data1[i]!=';'&&data1[i]!=',')
                d1[j++]=data1[i++];
            if(data1[i]==',')
                i++;
            if(data1[0]=='-')            //处理正负数
                j=-(int)fabs(atoi(d1));
            else
                j=atoi(d1);
            InsertNode(head1,k++,j);
        }
            
        i=0;
        k=0;
        while(data2[i]!=';')        //将数2用链表储存
        {
            for(j=0;j<10;j++)
                d2[j]=0;
            j=0;
            while(data2[i]!=';'&&data2[i]!=',')
                d2[j++]=data2[i++];
            if(data2[i]==',')
                i++;
            if(data2[0]=='-')        //处理正负数
                j=-(int)fabs(atoi(d2));
            else
                j=atoi(d2);
            InsertNode(head2,k++,j);
        }
        if(strlen(data1)>strlen(data2))        //较长的数作为被加数
            plus(head1,head2);
        else
            plus(head2,head1);
        DestroyNode(&head1);
        DestroyNode(&head2);
    }
    
    return 0;
}


/************************************************************

  基本算法:

  将一个大的整数分解成若干部分,每四位一部分,分别储存在链表的每个元素中.
  正数直接储存进去,而负数全部转换为负数然后储存进去. 然后从最后一个元素
  开始,对应相加,直到有一个链表的数据元素处理完为止.在相加的过程中,两个四
  位数相加有可能会出现五位数,正数和负数相加有可能会正负不一的情况,这些情
  况都要进行处理.另个在打印的时候对一些少于四位数的也要进行一下处理.


  实现过程中遇到的问题:

  早开始采用整型数据输入数据,每四位输入,而要采用逗号分开,两个数还要用分号
  分开,不太容易处理,后来在老师的指导下,采用字符串进行处理,非常顺利,基本可
  以处理一般的数,最后就是调试,对一些特殊的数进行处理,主发是处理相加的函数
  和打印输出的函数.

  测试数据:(数据以逗号分组,以分号结束,两个数字之间用空格分开)

        0; 0;
        0
        -2345,6789; -7654,3211;
        -1,0000,0000;
        -9999,9999; 1,0000,0000,0000;
        9999,0000,0001;
        1,0001,0001; -1,0001,0001;
        0
        1,0001,0001; -1,0001,0000;
        1;
        1234,5648,2345,6217; 5689,7565,3245,3576;
        6924,3213,5590,9793;
        9999,9999,9999,9999; 1,0000,0000,0000,00001;
        2,0000,0000,0000,0000;


************************************************************/

雁无留踪之意,水无取影之心
2008-03-15 23:27
PcrazyC
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:5652
专家分:0
注 册:2006-10-20
收藏
得分:0 
一位一位进行的话,速度肯定很慢,所以我采用了四位进行操作(你也可以进行更多位,自己把握)

雁无留踪之意,水无取影之心
2008-03-15 23:29
aipb2007
Rank: 8Rank: 8
来 自:CQU
等 级:贵宾
威 望:40
帖 子:2879
专家分:7
注 册:2007-3-18
收藏
得分:0 
用数组做,不过要事先假设输入数字最大位数。
以前的OJ题

程序代码:
#include <stdio.h>
#include <string.h> 

char a[105],b[105]; 

char* add(char *a,char *b){
    int i,j,k = 0,tmp[105],l1 = strlen(a),l2 = strlen(b);
    for (i = l1-1,j = l2-1;i >= 0 && j >= 0;--i,--j)        
        tmp[k++] = a[i]+b[j]-'0'-'0';    
    for (;i >= 0;--i)        
        tmp[k++] = a[i]-'0';    
    for (;j >= 0;--j)        
        tmp[k++] = b[j]-'0'; 
    
    tmp[k] = 0;    
    for (i = 0;i < k;++i){
        tmp[i+1] += tmp[i]/10;        
        tmp[i] %= 10;    
    } 
        
    if (!tmp[k])        
        --k;        
    for (i = 0;i <= k;++i)        
        a[i] = tmp[k-i] + '0';    
    a[k+1] = '\0';     
    
    return a;
} 

int main(){    
    char *r;    
    while (scanf("%s%s",a,b) != EOF){        
        r = add(a,b);
        printf("%s\n",r);
    }    
    return 0;
}


当然,这是纯粹从效率的角度出发,pcrazyc的模块组织更好。

Fight  to win  or  die...
2008-03-16 10:35
雪城白鸟
Rank: 1
来 自:吉林
等 级:新手上路
帖 子:22
专家分:0
注 册:2008-3-15
收藏
得分:0 
谢谢
我们才开始接触链表,还不知道怎么应用 我测试了一下你的代码,似乎没有返回值,但同样非常感谢你的帮助,以后有不懂的还希望多多帮忙    thanks for your help ,PcrazyC
2008-03-16 17:07
PcrazyC
Rank: 6Rank: 6
等 级:贵宾
威 望:29
帖 子:5652
专家分:0
注 册:2006-10-20
收藏
得分:0 
不会吧,怎么会没有输出呢.

你要严格按照我的输入格式才行
测试数据:(数据以逗号分组,以分号结束,两个数字之间用空格分开)

最后一段那有测试数据及相关的输入格式,你试下

雁无留踪之意,水无取影之心
2008-03-16 18:09
快速回复:求助: 任意大数相加怎么做?
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.039993 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved