笔试题练习(五)

简介:
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';
                String sum = "0";
                for (j = 0; j < n2; ++j)
                {
                    sum = add(sum,num1);
                }
                StringBuilder tmpSB = new StringBuilder(sum);
                for (j = i; j < len2 -1; ++j)
                {
                    tmpSB.append("0");
                }
                result = add(result,tmpSB.toString());
            }
        }

        return result;
    }    
    private static String add(String num1, String num2)
    {
        String result = "";
        int len1 = num1.length();
        int len2 = num2.length();
        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)
            {
                n1 = num1.charAt(i) - '0';
                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 (sum >= 10)
                {
                    nAddOn = 1;
                }
                else
                {
                    nAddOn = 0;
                }
                sb.append(sum % 10);
            }
        }
        
        if (nAddOn > 0)
        {
            sb.append(nAddOn);
        }
        
        sb.reverse();
        result = sb.toString();
        return result;
    }
    private static String factorial(int n)
    {
        String result = "1";
        for (int i = n; i >= 2; --i)
        {
            result = multipy(result,String.valueOf(i));
        }
        return result;
    }
    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;
            }
            else
                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; 
        } 
        return result; 
    }
复制代码
设最大数为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;
        }
        return result; 
        }
复制代码
等比数列的项数为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'
        }
        else
        {//八进制
            radix = 8;
            ++p;//跳过'0'
        }
    }
    while (*p != '\0')
    {
        if (radix == 16)
        {//16进制
            if (*p >='0' && *p <= '9')
            {
                result = result*radix + *p - '0';
            }
            else
            {//字母
                int tmp = toupper(*p);//大写化
                result = result*radix + tmp -'A'+10;
            }
        }
        else
        {//8或进制,不含字母
            result = result*radix + *p - '0';
        }
        ++p;
    }
    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中,并说明算法的时间复杂度

复制代码
/************************************************************************/
/* Author: phinecos Date:2009-05-27                                                                     */
/************************************************************************/
#include <iostream>
using namespace std;

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;

}
int main()
{
    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;
    return 0;
}
复制代码



本文转自Phinecos(洞庭散人)博客园博客,原文链接:http://www.cnblogs.com/phinecos/archive/2009/05/27/1490921.html 转载请自行联系原作者

目录
相关文章
|
网络协议 Java 调度
笔试题总结
32位机器上,以下结构的sizeof(P)为 struct A { int a; char b; int c; char d; } struct P { struct A w[2]; short b; struct A* p; } /*考察结构体对齐和填充: 结构体每个成员相对于结构体首地址的偏移量都是成员大小的整数倍,如果不是,编译器会自动在成员间填充。
993 0
|
Java
笔试题解答
/** * @author shishusheng * @date 2018/8/22 23:35 */ import java.util.
875 0
|
机器学习/深度学习
|
机器学习/深度学习 搜索推荐 索引

热门文章

最新文章