Author:一醉解千愁
From:
今天朋友给我出了一道题,说是怎么实现100位数字相乘?
据说这是微创的面试题目.
花了一个晚上终于弄出来一个实现方式.实现了加、减、乘、除.
其中以除的效率最低,暂时还没想到更好的办法.等想到了在更新吧.
算算前后花了大约6、7个小时,如果在面试中碰见这种题目那可如何是好啊.
把代码贴出来,有兴趣的可以看看,大家讨论下是否有更好的实现方法.
以下为代码:
/*
* Description:超长整型数字操作(加、减、乘、除)
* Author:czhenq
* Date:2006-8-30
* MSN:czhenq@hotmail.com
* E-Mail:czhenq@gmail.com
*/
using System;
using System.Collections.Generic;
using System.Text;
namespace CWing
{
public class SuperInteger
{
private String integer = "";
public SuperInteger(String bigInteger)
{
integer = bigInteger;
}
public String Integer
{
get
{
return integer;
}
set
{
integer = value;
}
}
public Int32 Length
{
get
{
return integer.Length;
}
}
public static SuperInteger operator +(SuperInteger a, SuperInteger b)
{
return new SuperInteger(Add(a.Integer, b.Integer));
}
public static SuperInteger operator *(SuperInteger a, SuperInteger b)
{
return new SuperInteger(Multiplication(a.Integer, b.Integer));
}
public static SuperInteger operator -(SuperInteger a, SuperInteger b)
{
return new SuperInteger(Subtract(a.Integer,b.Integer));
}
public static SuperInteger operator /(SuperInteger a, SuperInteger b)
{
if (b.Integer == "0")
{
return new SuperInteger("0");
}
if (b.Integer == "1")
{
return a;
}
if (a == b)
{
return new SuperInteger("1");
}
if (a < b)
{
return new SuperInteger("0");
}
List list = new List();
SuperInteger temp = b;
SuperInteger end = new SuperInteger("1");
for (SuperInteger i = new SuperInteger("2"); i < a; i++)
{
if ((i * temp) == a)
{
list.Add(i);
break;
}
else if ((i * temp) > a)
{
end = i;
break;
}
list.Add(i);
temp = (i * temp);
}
SuperInteger returnValue = new SuperInteger("1");
for (int i = 0; i < list.Count; i++)
{
returnValue = returnValue * list[i];
}
Console.WriteLine(end.Integer);
Console.WriteLine(returnValue.Integer);
Console.WriteLine((returnValue * end).Integer);
for (SuperInteger i = returnValue; i < (returnValue * end);i++)
{
if ((i * b) == a)
{
return i;
}
else if ((i * b) > a)
{
return (i - new SuperInteger("1"));
}
}
return returnValue;
}
public static SuperInteger operator ++(SuperInteger a)
{
a = a + new SuperInteger("1");
return a;
}
public static SuperInteger operator --(SuperInteger a)
{
a = a - new SuperInteger("1");
return a;
}
public static Boolean operator >(SuperInteger a, SuperInteger b)
{
SuperInteger result = a - b;
if (result.Integer.StartsWith("-"))
{
return false;
}
else
{
return true;
}
}
public static Boolean operator <(SuperInteger a, SuperInteger b)
{
return (b > a);
}
public static Boolean operator ==(SuperInteger a, SuperInteger b)
{
SuperInteger result = a - b;
if (result.Integer == "0")
{
return true;
}
else
{
return false;
}
}
public static Boolean operator !=(SuperInteger a, SuperInteger b)
{
SuperInteger result = a - b;
if (result == new SuperInteger("0"))
{
return true;
}
else
{
return false;
}
}
private static String Subtract(String a, String b)
{
if (a.Length < b.Length)
{
a = GetZero(b.Length - a.Length) + a;
}
else if (a.Length > b.Length)
{
b = GetZero(a.Length - b.Length) + b;
}
List list = new List();
Int32 carry = 0;
for (int i = (a.Length - 1); i >= 0; i--)
{
Result r = SubtractChar(int.Parse(a[i].ToString()), int.Parse(b[i].ToString()), carry);
carry = r.carry;
list.Add(r.Value);
}
String str = "";
for (int i = list.Count - 1; i >= 0; i--)
{
str += list[i];
}
if (carry >= 0)
{
str = str.TrimStart("0".ToCharArray());
if (str.Length == 0)
str = "0";
return str;
}
else
{
return "-" + Subtract("1" + GetZero(str.Length), str).TrimStart("0".ToCharArray());;
}
}
private static Result SubtractChar(int a, int b, int carry)
{
Result r = new Result();
if (a >= (b - carry))
{
r.Value = (a - b + carry).ToString();
r.carry = 0;
}
else
{
r.Value = (a - b + carry + 10).ToString(); ;
r.carry = -1;
}
return r;
}
private static String Multiplication(String a, String b)
{
List list2 = new List();
int n = 0;
for (int i = b.Length - 1; i >= 0; i--)
{
List list = new List();
int carry = 0;
string str = "";
for (int j = a.Length - 1; j >= 0; j--)
{
Result r = CharMultiplication(Convert.ToInt32(a[j].ToString()), Convert.ToInt32(b[i].ToString()), carry);
carry = r.carry;
list.Add(r.Value);
}
if (carry > 0)
{
list.Add(carry.ToString());
}
for (int k = list.Count - 1; k >= 0; k--)
{
str += list[k];
}
str += GetZero(n);
list2.Add(str);
n++;
}
string result = "0";
for (int i = 0; i < list2.Count; i++)
{
result = Add(list2[i], result);
}
result = result.TrimStart("0".ToCharArray());
if (result.Length == 0)
result = "0";
return result;
}
private static Result CharMultiplication(int a, int b, int carry)
{
int ir = a * b + carry;
Result r = new Result();
r.Value = (ir % 10).ToString();
r.carry = (ir / 10);
return r;
}
private static String Add(String a, String b)
{
if (a.Length > b.Length)
{
b = GetZero(a.Length - b.Length) + b;
}
else if (a.Length < b.Length)
{
a = GetZero(b.Length - a.Length) + a;
}
List list = new List();
Int32 carry = 0;
for (int i = a.Length - 1; i >= 0; i--)
{
Result r = CharAdd(int.Parse(a[i].ToString()), int.Parse(b[i].ToString()), carry);
list.Add(r.Value);
carry = r.carry;
}
if (carry > 0)
{
list.Add(carry.ToString());
}
String str = "";
for (int i = list.Count - 1; i >= 0; i--)
{
str += list[i];
}
str = str.TrimStart("0".ToCharArray());
if(str.Length == 0)
{
str = "0";
}
return str;
}
private static Result CharAdd(int a, int b, Int32 carry)
{
int ir = a + b + carry;
Result r = new Result();
r.Value = (ir % 10).ToString();
r.carry = (ir / 10);
return r;
}
private static String GetZero(int number)
{
string r = "";
for (int i = 0; i < number; i++)
{
r += "0";
}
return r;
}
private struct Result
{
public String Value;
public Int32 carry;
}
}
}
代码太长了,把源文件放上来了:
DOWN 