Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我的老超时 麻烦那位高手帮忙解决一下 小弟感激不尽!

Posted by SJ_wlf at 2010-03-24 14:15:08 on Problem 1001
#include<iostream>
#include<string>
using namespace std;

int M,number;                           // 计录小数点的位数
int DotLocation(string str)           // 计算小数点位数
{
    int lgth = str.length()-1;
	int location = str.find(".");     // 判断是否有小数点
	if(location!=-1)
	{
		if(str.at(lgth) == '0')       // 有小数点且尾部数字为零
		{
		   int i = lgth;
           while(i>=0)
		   {
			   if(str.at(i)!='0')     // 从后往前第一个不为零的字符停止
				   break;
			   i--;
		   }
		   return i - location;       // 返回小数点位数
		}
		else                          // 有小数点但尾部不为零
		{
			return lgth - location;
		}
	}
	else                              // 字符串中没有小数点
	    return -1;
}

void DealArray(int *a,int len)        // 对整形数组的处理
{
    int i;
	for(i = len-1;i>0;i--)
	{
		if(a[i]>=10)
		{
			a[i-1] = a[i-1] + a[i]/10;
			a[i] = a[i]%10;
		}
	}
}

void OutPut(string str,int n)          // 添加小数点输出函数
{
	 int i;
	 number = n*number;                // 小数点有多少位
	 int k = str.length();             
	 if(number > 0)
	 {
	     if(number >= k)
		 {
		    str.insert(0,".");
		    if(number > k)
		       for(i=1;i<=number - k;i++)
			       str.insert(i,"0");
			if(str.at(str.length()-1)=='0')
			{
				i = str.length() - 1;
				while(i>=0)
				{
					i--;
					if(str.at(i)!='0')
						break;
				}
			    if(str.at(i) == '.')
				    str.substr(0,i);
			    else
				    str.substr(0,i+1);
			    cout<<str<<endl;
			}
			else
			{
				cout<<str<<endl;
			}
		 }

	    else
		{
		    str.insert(k-number,".");
		    if(str.at(str.length()-1)=='0')
			{
			    i = str.length()-1;
			    while(i>=0)
				{
				   i--;
				   if(str.at(i)!='0')
					   break;
				}
			    if(str.at(i) == '.')
		           str.substr(0,i);
		        else
			       str.substr(0,i+1);
				cout<<str<<endl;
			}
			else
			{
			    cout<<str<<endl;
			}
		}
	 }
	 else
	 {
		 cout<<str<<endl;
	 }
}

void StrConvertInt(string str,int *a)              // 字符串转为整形数组功能
{
	string str1;
	int i;
	for(i = 0;i<=str.length()-1;i++)
	{
        str1 = str.substr(i,1);
        a[i] = atoi(str1.c_str());
	}
}

void Mult(int *a,int *s,int N,int len1,int len2)
{
    int i,j;
	string str = "";
	char*str1 = new char[5];
	int *f = new int[len2];
	int *sum = new int[len2];                         // 动态分配数组
	int *b = new int[len2];
	for(j = 0;j<len2;j++)                                       // 初始化
		    sum[j] = 0;
	for(i = len1-1;i >= 0;i--)
	{
		for(j=0;j <= len2-1;j++)
		{
			b[j] = sum[j];
		}

		for(j = len2-1;j >= 0;j--)
		{
            f[j] = a[i]*s[j]; 
		}
       	DealArray(f,len2);
		for(j = len2-1;j > 0;j--)
		{	
			 sum[j] = f[j] + b[j-1];
		}
        sum[0] = f[0];
        DealArray(sum,len2);
        sprintf(str1,"%d",sum[len2 - 1]);
		str = str1 + str;
	}
	for(j = len2 -2;j>=0;j--)
	{
		sprintf(str1,"%d",sum[j]);
		str = str1 + str;
	}
	delete []str1;
	delete []f;
	delete []sum;
	delete []b;
	int *g = new int[str.length()];
	StrConvertInt(str,g);
	if(N!=2)
		Mult(a,g,N-1,len1,str.length());
	else
        OutPut(str,M); 
	delete []g;
}

string DotCut(string str)                                       // 去掉小数点的函数
{
	int i;
	string str1,str2;
    for(i = 0;i<=str.length()-1;i++)
	{
		if(str.at(i)=='.')
		{
		    str1 = str.substr(0,i);
			str2 = str.substr(i+1,str.length()-i-1);
			break;
		}
	}
	return str1+str2;
}

string DealStr(string str)
{
    number = DotLocation(str);
	int i;
	string str1,str2,str3;

	if(number == -1)                                             // 无小数点
	{
		return str;
	}

    else                                                         // 有小数点
	{
        if(str.at(0) == '0')                                     // 首部是零的情况         
		{
            for(i = 0;i<str.length();i++)                        
			{
				if(str.at(i)!='0'&&str.at(i)!='.')               // 从首部开始直到第一个不为零结束
				{
                     str1 = str.substr(i,str.length()-1);        // 子字符串去掉原字符串的首部零还有小数点 
					 break;
				}
			}

			if(str1.at(str1.length()-1) == '0')                  // 子字符串尾部也是零   
			{
			    for(i = str1.length()-1;i>=0;i--)                // 从尾部开始直到第一个不为零为止    
				{
				    if(str1.at(i)!='0')             
					{
					    str2 = str1.substr(0,i+1);               // 截取子字符串去掉尾部零
						break;
					}
				}
				return str2;                                         
			}
			else                                                 // 字符串尾部不为零
                return str1;
		}
		else                                                     // 首部不是零的情况
		{
            if(str.at(str.length()-1) == '0')                    // 结尾是零的情况
			{
			    for(i = str.length()-1;i>=0;i--)                 // 从尾部开始第一个不为零的字符为止
				{
				    if(str.at(i)!='0')
					{
					    str1 = str.substr(0,i+1);
						break;
					}
				}
				str2 = DotCut(str1);                             // 去掉小数点
				return str2;
			} 
			else                                                 // 尾部不是零的情况
			{
				str1 = DotCut(str);                              // 去掉小数点
				return str1;
			}
		}
    }
}

int main(int args[],char *argc[])
{
	string str,str1;
	int len,N;
    int *a;
	while(cin>>str>>N)
	{    
		 M = N;                                                   // 记录N 为计算结果的小数点时用
		 str1 = DealStr(str);
	     len = str1.length();
	     a = new int[len];
	     StrConvertInt(str1,a);                                   // 字符串转化为整形数组
	     Mult(a,a,N,len,len);
	}
    delete []a;
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator