1, 对任意输入的正整数N,编写程序求N!的尾部连续0的个数,并指出计算复杂度。如:18!=6402373705728000,尾部连续0的个数是3。(不用考虑数值超出计算机整数界限的问题)
解法1:(直接大数计算N!)
<!--<br />
<br />
Code highlighting produced by Actipro CodeHighlighter (freeware)<br />
http://www.CodeHighlighter.com/<br />
<br />
-->
/**
*
*@authorphinecos
*@since2005-05-27
*/
publicclasstest
{
privatestaticStringmultipy(Stringnum1,Stringnum2)
{//大数乘法
Stringresult="0";
inti,j,n1,n2;
intlen1=num1.length();
intlen2=num2.length();
if(len1<len2)
{
for(i=len1-1;i>=0;--i)
{
n1=num1.charAt(i)-'0';
Stringsum="0";
for(j=0;j<n1;++j)
{
sum=add(sum,num2);
}
StringBuildertmpSB=newStringBuilder(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';
Stringsum="0";
for(j=0;j<n2;++j)
{
sum=add(sum,num1);
}
StringBuildertmpSB=newStringBuilder(sum);
for(j=i;j<len2-1;++j)
{
tmpSB.append("0");
}
result=add(result,tmpSB.toString());
}
}
returnresult;
}
privatestaticStringadd(Stringnum1,Stringnum2)
{
Stringresult="";
intlen1=num1.length();
intlen2=num2.length();
intnAddOn=0;
inti,j,n1,n2,sum;
StringBuildersb=newStringBuilder();
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);
}
}
elseif(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();
returnresult;
}
privatestaticStringfactorial(intn)
{
Stringresult="1";
for(inti=n;i>=2;--i)
{
result=multipy(result,String.valueOf(i));
}
returnresult;
}
privatestaticintcountNFactZeroes(intn)
{
Stringresult=factorial(n);//N!
System.out.println(result);
intcount=0;
for(inti=result.length()-1;i>=0;--i)
{
if(result.charAt(i)=='0')
{
++count;
}
else
break;
}
returncount;
}
publicstaticvoidmain(String[]args)throwsException
{
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)
<!--<br />
<br />
Code highlighting produced by Actipro CodeHighlighter (freeware)<br />
http://www.CodeHighlighter.com/<br />
<br />
-->privatestaticintcountNFactZeroes2(intn)
{
inti,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;
}
}
returnresult;
}
解法3:N不变,pow5以5的幂递增,此算法的思想是求出N以内所有被5整除的数的个数,所有被25整除的个数(在5的基础上多出了一个5因子),所有被125整除的个数(在25的基础上多出了一个5因子)。。。
<!--<br />
<br />
Code highlighting produced by Actipro CodeHighlighter (freeware)<br />
http://www.CodeHighlighter.com/<br />
<br />
-->privatestaticintcountNFactZeroes3(intn)
{
intpow5,result=0;
for(pow5=5;pow5<=n;pow5*=5)//此处的循环次数为LOG5(N)
{
result+=n/pow5;
}
returnresult;
}
设最大数为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,即相加,便得到以下算法
<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->privatestaticintcountNFactZeroes4(intn)
{
intresult=0;
intm=n/5;
while(m>0)
{
result+=m;
m=m/5;
}
returnresult;
}
等比数列的项数为
log5(N),即为循环的次数,故复杂度为log5(N)
2,题目:请编写一个 C 函数,该函数将给定的一个字符串转换成整数
<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->/************************************************************************/
/*Author:phinecosDate:2009-05-27*/
/************************************************************************/
#include<iostream>
#include<cassert>
usingnamespacestd;
intStringToInt(constchar*str)
{//考虑八进制,十六进制,十进制
assert(str!=NULL);
assert(strlen(str)!=0);
intresult=0;
intsign=1;//符号位
intradix=10;//默认是进制
constchar*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
{//字母
inttmp=toupper(*p);//大写化
result=result*radix+tmp-'A'+10;
}
}
else
{//8或进制,不含字母
result=result*radix+*p-'0';
}
++p;
}
returnresult*sign;
}
intmain()
{
cout<<StringToInt("-355643")<<endl;
cout<<StringToInt("-0x200")<<endl;
cout<<StringToInt("-0123")<<endl;
cout<<StringToInt("-0x7FFFFFFF")<<endl;
return0;
}
3,已知两个字符数组,char a[m],b[n],m>n>1000,写程序将a中存在,但b中不存在的元素放入字符数组c中,并说明算法的时间复杂度
<!--<br /><br />Code highlighting produced by Actipro CodeHighlighter (freeware)<br />http://www.CodeHighlighter.com/<br /><br />-->/************************************************************************/
/*Author:phinecosDate:2009-05-27*/
/************************************************************************/
#include<iostream>
usingnamespacestd;
boolisExist[256]={false};//256个字符是否存在的标志
char*merge(chara[],intn,charb[],intm)
{
char*c=newchar[m+n];
inti,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中不存在的加入新数组
charch;
for(i=0;i<256;++i)
{
if(isExist[i]==true)
{
ch=(char)i;
c[k++]=ch;
}
}
c[k]='/0';
returnc;
}
intmain()
{
chara[]={'a','c','4','s','v','y','Y','C','E'};
charb[]={'c','y',',','u','r'};
intn=sizeof(a)/sizeof(char);
intm=sizeof(b)/sizeof(char);
char*c=merge(a,n,b,m);
cout<<c<<endl;
delete[]c;
return0;
}
分享到:
相关推荐
嵌入式笔试题练习
中国银行最全笔试资料历年笔试真题11-19年考试完整试题及答案解析+五大银行招聘考试练习题库(30多份pdf) 0-中国银行历年笔试真题11-18年 1-中国银行复习精华讲义 2-中国银行2019招聘考试完整试题及答案解析 3-五大...
ACCP6.0Y2笔试题仅供练习ACCP6.0Y2笔试题仅供练习
全国计算机等级考试笔试题练习,带有答案
2007-02-27-全国计算机等级考试笔试题练习 .rar
应聘笔试题
幼小中教资笔试真题练习(附参考答案).pdf
多个Java笔试题适合急于找工作的应届生
数据库笔试题及答案 数据库练习题题库 不错的SQL笔试题(含参考答案) 共16页.pdf
机测并精心整理筛选的33道MySQL笔试题(附带答案、表结构与数据),安装数据库后导入test.sql文件即可练习
经典sql练习,几道经典的SQL笔试题题目。sql就在于多多练习
C++程序员笔试题,我觉得很好,对刚开始学习的人是一份很好的资料
2013年四川移动校招笔试题 2013年中国移动广东公司招聘笔试试题及答案 2014年中国移动招聘笔试试题及答案 2015年中国移动招聘笔试试题及答案 移动笔试真题之技术类--浙江移动金华分公司无线网优测试试题 移动笔试...
教师资格证笔试练习题五答案解析.docx
关于c语言面试题的一些收集资料: C语言笔试题汇总.doc C语言笔试大全_本人收藏.doc C语言编程练习题.doc
KPMG笔试题下载,包括一套练习样题和两套题
java面试笔试题库java软件设计java笔试题大集合及答案文档资料合集300MB“ 100家大公司java笔试题汇总.doc 125条常见的java 面试笔试题大汇总.pdf 2011最新整理java经典代码.doc 25个经典的Spring面试问答.docx 8张...
google笔试题,经典的笔试题,在练习中提高!that ‘s all,thank you
4-中国农业发展银行招聘考试练习题库(30多份pdf)(银行考试题库和各模块练习题).rar 5-时事政治and金融热点and金融大事记部分.rar 中国农业发展银行2019招聘笔试完整真题及答案解析.zip 信息技术类专用之技术类知识...
中兴笔试题 大家可以先练习一下 做好准备 大部分比较基础