博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
笔试题练习（五）
阅读量：6152 次
发布时间：2019-06-21

本文共 5651 字，大约阅读时间需要 18 分钟。

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 转载请自行联系原作者
你可能感兴趣的文章
几道高级前端面试题解析
查看>>
H3C交换机的端口隔离
查看>>
Java实现多线程的两种方式比较及区别
查看>>
What is Babel?
查看>>
一物一码新零售下，企业该如何发展
查看>>
Vue 2.0学习笔记：创建Button组件
查看>>
【漫画】关于容器，你是否踩过很多坑，要吐好多苦水？
查看>>
搭建模型第一步：你需要预习的NumPy基础都在这了
查看>>
Spring IOC 容器源码分析 - 填充属性到 bean 原始对象
查看>>
远程文件同步详解(Remote File Sync)
查看>>
支付宝推9.9版本，化身贴身“机器人管家”
查看>>
Windows Linux 子系统可以在资源管理器中打开
查看>>
CSS 预处理器（框架）初探：Sass、LESS 和 Stylus
查看>>
融合发展 江苏省未来网络创新研究院与新华三再牵手
查看>>
7月8日来造就，聆听《未来简史》作者与诸位大牛的激烈思辨
查看>>
李开复：AI 创业的十个真相 | 深度
查看>>
基于阿里的Node全栈之路（八）Nodejs性能监控和优化
查看>>
拥抱物联网，将数据点石成金
查看>>
重磅 | 中国发布世界首台10比特光量子计算机
查看>>
统一量子世界与宏观世界的新数学在哪里？
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2025-01-06 11:33:29   当前IP: 18.226.166.207   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我