日期:2014-05-20  浏览次数:20847 次

求解华为面试题
前两天去参加了一次华为的社会招聘会,面试官现场出了这样一道题:
请使用代码计算: 1234567891011121314151617181920*2019181716151413121110987654321 ,当时蒙了,求解啊?

------解决方案--------------------
结果=2492816912877266687794240983772975935013386905490061131076320
这是大数的乘法。
原理:
1、用字符串来存储大数
2、进行大数的乘法运算很简单.我这里说下我的运算方式.
3、方式:
a、首先移动大数的小数点(有的话)把大数扩展成一个正整数.
b、对大数按每9个字长来截取分别进行相乘(为什么会是9,因为2个9位数的正整数相乘结果不会超过多少位数,这个问题留着你思考,而这个乘的过程我们可以交给计算机的64位整数运算完成,例如VB.NET的Long类型)注意乘的过程移位的问题,即结果后是否需要添加多个0.
c、最后把所有截取的大数相乘的结果相加即可.
d、对于a把小数点移回去.
下面是VBNET源代码:(BigNumberMul)
 
VB.NET code
Public Function BigNumberMul(ByVal Mul1 As String, ByVal Mul2 As String) As String '支持小数相乘。也支持负数
        Dim mul11 As String = ""
        Dim mul12 As String = ""
        Dim mul21 As String = ""
        Dim mul22 As String = ""
        Dim t As Boolean = False
        Dim i As Integer
        Dim is2(1) As Boolean
        If Mul1 = "" Or Mul2 = "" Or BigGetNumber(Mul1, mul11, mul12, is2(0)) = False Or BigGetNumber(Mul2, mul21, mul22, is2(1)) = False Then
            Return ""
        End If
        i = mul12.Length - mul22.Length
        If i > 0 Then
            mul22 += StrDup(i, "0")
        Else
            mul12 += StrDup(-i, "0")
        End If
        i = mul22.Length * 2
        mul11 = BigNumberMul_(mul11 + mul12, mul21 + mul22)
        Dim j As Integer = i - mul11.Length + 1
        If j > 0 Then
            mul11 = StrDup(j, "0") + mul11
        End If
        If i > 0 Then
            mul22 = Mid(mul11, mul11.Length - i + 1, i)
            mul11 = Mid(mul11, 1, mul11.Length - i)
            i = mul22.Length
            While mul22.EndsWith("0")
                i -= 1
                mul22 = Mid(mul22, 1, i)
            End While
            If i > 0 Then
                mul11 += "." + mul22
            End If
        End If
        If is2(1) <> is2(0) Then
            mul11 = "-" + mul11
        End If
        Return mul11
    End Function
 Public Function BigNumberMul_(ByVal Mul1 As String, ByVal Mul2 As String) As String '正整数相乘
        Dim size1 As Integer = Mul1.Length
        Dim size2 As Integer = Mul2.Length
        Dim Mulret As String = ""
        Dim i As Integer = size1 - size2
        If i < 0 Then
            Mulret = Mul1
            Mul1 = Mul2
            Mul2 = Mulret
            i = size1
            size1 = size2
            size2 = i
            Mulret = ""
        End If
        i = 7 - size2 Mod 7
        Mul2 = StrDup(i, "0") + Mul2
        i = 7 - size1 Mod 7
        Mul1 = StrDup(i, "0") + Mul1
        size2 = Mul2.Length - 6
        Dim tempi As Int64 = 0
        Dim tempj As Int64 = 0
        Dim temp As Int64 = 0
        Dim j As Integer = 0
        Dim tempstr As String = ""
        Dim ret() As String = Nothing
        Dim Number As Integer = 0
        size1 = Mul1.Length
        While size2 > 0
            ReDim Preserve ret(Number)
            ret(Number) = ""
            tempi = CDbl(Mid(Mul2, size2, 7))
            j = size1 - 6
            temp = 0
            While j > 0
                tempj = CDbl(Mid(Mul1, j, 7)) * tempi + temp
                temp = tempj \ 10000000
                tempstr = CStr(tempj Mod 10000000)
                i = 7 - tempstr.Length
                tempstr = StrDup(i, "0") + tempstr
                ret(Number) = tempstr + ret(Number)
                j = j - 7
            End While
            ret(Number) += StrDup(Number * 7, "0")
            If temp <> 0 Then
                ret(Number) = CStr(temp) + ret(Number)
            Else
                i = ret(Number).Length
                While ret(Number).StartsWith("0")
                    i -= 1
                    ret(Number) = Mid(ret(Number), 2, i)
                End While
                If i = 0 Then
                    ret(Number) = "0"
                End If
            End If
            size2 = size2 - 7
            Number += 1
        End While
        Mulret = ret(0)
        i = ret.Length
        While i > 1
            i -= 1
            Mulret = BigNumberAdd_(Mulret, ret(i))
        End While
        Return Mulret
    End Function
 Public Function BigGetNumber(ByVal Number As String, ByRef RetN As String, ByRef retSmall As String, ByRef Is负数 As Boolean) As Boolean '非数字返回假.RetN返回的整数部分,retSmall小数部分
        Dim i As Integer = 0
        While i <> -1
            Number = Number.Replace(" ", "")
            i = Number.IndexOf(" ")
        End While
        i = Number.Length
        If i = 0 Then
            Return False
        End If
        Is负数 = False
        If Number.StartsWith("-") Then
            If i = 1 Then
                Return False
            Else
                Is负数 = True
                Number = Mid(Number, 2, i - 1)
            End If
        End If
        i = Number.IndexOf(".")
        If i > 0 Then
            RetN = Mid(Number, 1, i)
            retSmall = Mid(Number, i + 2, Number.Length - i - 1)
        Else
            RetN = Number
            retSmall = ""
        End If
        Number = RetN + retSmall
        i = Number.Length
        Dim temp As String = ""
        While i > 0
            temp = Mid(Number, i, 1)
            If temp < "0" Or temp > "9" Then
                Return False
            End If
            i -= 1
        End While
        i = RetN.Length
        While i > 1
            If RetN.StartsWith("0") = False Then
                Exit While
            End If
            i -= 1
            RetN = Mid(RetN, 2, i)
        End While
        i = retSmall.Length
        While i > 0
            If Mid(retSmall, i, 1) = "0" Then
                i -= 1
                retSmall = Mid(retSmall, 1, i)
            Else
                Exit While
            End If
        End While
        Return True
    End Function
    Public Function BigNumberAdd_(ByVal Add1 As String, ByVal Add2 As String) As String '只支持正整数的相加
        Dim size1 As Integer = Add1.Length
        Dim size2 As Integer = Add2.Length '14位
        Dim Add As String = ""
        Dim temp As String = ""
        Dim i As Integer = size1 - size2
        If i > 0 Then
            Add2 = StrDup(i, "0") + Add2
        ElseIf i < 0 Then
            Add1 = StrDup(-i, "0") + Add1
            size1 = size2
        End If
        size2 = 0
        While size1 > 14
            size1 -= 14
            temp = CStr(CLng(Mid(Add1, size1 + 1, 14)) + CLng(Mid(Add2, size1 + 1, 14)) + size2)
            i = 14 - temp.Length
            If i > 0 Then
                temp = StrDup(i, "0") + temp
                size2 = 0
            ElseIf i = -1 Then
                size2 = CInt(Mid(temp, 1, 1))
                temp = Mid(temp, 2, 14)
            Else
                size2 = 0
            End If
            Add = temp + Add
        End While
        temp = CStr(CLng(Mid(Add1, 1, size1)) + CLng(Mid(Add2, 1, size1)) + size2)
        Add = temp + Add
        i = Add.Length
        While i > 1
            If Add.IndexOf("0") <> 0 Then
                Exit While
            End If
            i -= 1
            Add = Mid(Add, 2, i)
        End While
        Return Add
    End Function