筆試題練習（五）

1, 對任意輸入的正整數N，編寫程式求N!的尾部連續0的個數，并指出計算複雜度。如：18！＝6402373705728000，尾部連續0的個數是3。（不用考慮數值超出計算機整數界限的問題）

解法1：（直接大數計算N!）

複制代碼

/**

 * 

 * @author phinecos

 * @since 2005-05-27

 */

public class test 

{

    private static String multipy(String num1, String num2)

    {//大數乘法

        String result = "0";

        int i,j,n1,n2;

        int len1 = num1.length();

        int len2 = num2.length();

        if (len1 < len2)

        {

            for (i = len1 -1; i >=0; --i)

            {

                n1 = num1.charAt(i) - '0';

                String sum = "0";

                for (j = 0; j < n1; ++j)

                {

                    sum = add(sum,num2);

                }

                StringBuilder tmpSB = new StringBuilder(sum);

                for (j = i; j < len1 -1; ++j)

                    tmpSB.append("0");

                result = add(result,tmpSB.toString());

            }

        }

        else

            for (i = len2 -1; i >=0; --i)

                n2 = num2.charAt(i) - '0';

                for (j = 0; j < n2; ++j)

                    sum = add(sum,num1);

                for (j = i; j < len2 -1; ++j)

        return result;

    }    

    private static String add(String num1, String num2)

    {

        String result = "";

        int nAddOn = 0;

        int i,j,n1,n2,sum;

        StringBuilder sb = new StringBuilder();

        for (i = len1 - 1,j = len2 - 1 ; i >= 0 && j >= 0; --i,--j)

            n1 = num1.charAt(i) - '0';

            n2 = num2.charAt(j) - '0';

            sum = n1 + n2 + nAddOn;

            if (sum >= 10)

                nAddOn = 1;

            else

                nAddOn = 0;

            sb.append(sum % 10);

        if (len1 > len2)

            for (; i >= 0; --i)

                sum = n1 + nAddOn;

                if (sum >= 10)

                    nAddOn = 1;

                else

                    nAddOn = 0;

                sb.append(sum % 10);

        else if (len2 > len1)

            for (; j >= 0; --j)

                n2 = num2.charAt(j) - '0';

                sum = n2 + nAddOn;

        if (nAddOn > 0)

            sb.append(nAddOn);

        sb.reverse();

        result = sb.toString();

    }

    private static String factorial(int n)

        String result = "1";

        for (int i = n; i >= 2; --i)

            result = multipy(result,String.valueOf(i));

    private static int countNFactZeroes(int n)

        String result = factorial(n);//N!

        System.out.println(result);

        int count = 0;

        for (int i = result.length()-1; i >= 0; --i)

            if (result.charAt(i) == '0')

                ++count;

                break;

        return count;

    public static void main(String[] args) throws Exception

        System.out.println(countNFactZeroes(18));

}

解法2：連續K個0，則說明是10^K的倍數，即(2×5)^ K= 2^K× 5^K；待求的數為N*(N-1)(N-2)………1，由于每兩個數至少可以分解出1個2，2肯定比5多，是以K的個數取決于上式的分解因子中有幾個5的問題；能拆解出5的隻可能是5的倍數，而能拆解出多少個5則看這個數是5的幾次方的倍數了。時間複雜度是O（nlogn）

    private static int countNFactZeroes2(int n) 

        int i,j,result=0;

        for(i = 5; i <= n; i += 5) // 循環次數為n/5

        {//隻針對可以整除5的分解因子

            for(j = i; j%5 == 0; j /= 5) // 此處的最大循環次數為 LOG5(N)

            {//目前分解因子可以整除幾個5

                ++result;

            } 

        } 

        return result; 

解法3：N不變，pow5以5的幂遞增，此算法的思想是求出N以内所有被5整除的數的個數，所有被25整除的個數（在5的基礎上多出了一個5因子），所有被125整除的個數（在25的基礎上多出了一個5因子）。。。

    private static int countNFactZeroes3(int n) 

        int pow5,result=0; 

        for(pow5 = 5; pow5 <= n; pow5 *= 5) // 此處的循環次數為LOG5(N)

            result += n / pow5; 

設最大數為N, 設5^(n+1)  > N  >= 5^n 

[N/5] + [N/(5^2)] + [N/(5^3)] + ... + [N/(5^n)] 即為連續0的個數

上述式子的項數為log5(N)，即為循環的次數，故複雜度為log5(N)

解法4：由解法3可得如下：

[N/5] + [N/(5^2)] + [N/(5^3)] + ... + [N/(5^n)]

=[N/5] + [[N/5]/5] + [ [[N/5]/5]/5] + ... + [。。。]

=A1+ [A1/5] + [A2/5] + ... + [An-1/5]

即上述各項構成等比數列，An=An-1/5，等比為1/5

即對A1反複除5，隻要其大于0，即相加，便得到以下算法

    private static int countNFactZeroes4(int n) 

        int result=0; 

        int m = n/5;

        while (m > 0)

            result += m;

            m = m/5;

等比數列的項數為log5(N)，即為循環的次數，故複雜度為log5(N)

2,題目： 請編寫一個 C 函數，該函數将給定的一個字元串轉換成整數

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

/* Author: phinecos Date:2009-05-27                                                                     */

#include <iostream>

#include <cassert>

using namespace std;

int StringToInt(const char* str)

{//考慮八進制，十六進制，十進制

    assert(str != NULL);

    assert(strlen(str) != 0);

    int result = 0;

    int sign = 1;//符号位

    int radix = 10;//預設是進制

    const char *p = str;

    if (*p == '-')

    {//負數

        sign = -1;

        ++p;

    if (*p == '0')

    {//以'0'開頭，或者是八進制，或者是十六進制

        if ((*(p+1) == 'x') || (*(p+1) == 'X'))

        {//16進制

            radix = 16;

            p += 2;//跳過'0x'

        {//八進制

            radix = 8;

            ++p;//跳過'0'

    while (*p != '\0')

        if (radix == 16)

            if (*p >='0' && *p <= '9')

                result = result*radix + *p - '0';

            {//字母

                int tmp = toupper(*p);//大寫化

                result = result*radix + tmp -'A'+10;

        {//8或進制,不含字母

            result = result*radix + *p - '0';

    return result * sign;

int main()

    cout << StringToInt("-355643") << endl;

    cout << StringToInt("-0x200") << endl;

    cout << StringToInt("-0123") << endl;

    cout << StringToInt("-0x7FFFFFFF") << endl;

    return 0;

3,已知兩個字元數組，char a[m],b[n],m>n>1000,寫程式将a中存在，但b中不存在的元素放入字元數組c中，并說明算法的時間複雜度

bool isExist[256] = {false};//256個字元是否存在的标志

char* merge(char a[], int n, char b[],int m)

    char *c = new char[m+n];

    int i,k = 0;

    //判斷數組a中哪些字元存在

    for (i = 0; i < n; ++i)

        isExist[a[i]] = true;

    //判斷數組b中哪些字元存在

    for (i = 0; i < m; ++i)

        if (isExist[b[i]] == true)

            isExist[b[i]] = false;

    //a中存在，b中不存在的加入新數組

    char ch; 

    for (i = 0; i < 256; ++i)

        if (isExist[i] == true)

            ch = (char)i;

            c[k++] = ch;

    c[k] = '\0';

    return c;

    char a[] = {'a','c','4','s','v','y','Y','C','E'};

    char b[] = {'c','y',',','u','r'};

    int n = sizeof(a) / sizeof(char);

    int m = sizeof(b) / sizeof(char);

    char *c = merge(a,n,b,m);

    cout << c << endl;

    delete [] c;

本文轉自Phinecos(洞庭散人)部落格園部落格，原文連結：http://www.cnblogs.com/phinecos/archive/2009/05/27/1490921.html 轉載請自行聯系原作者