笔试题练习（五）

xiaoxiao2026-08-07 16

1, 对任意输入的正整数N，编写程序求N!的尾部连续0的个数，并指出计算复杂度。如：18！＝6402373705728000，尾部连续0的个数是3。（不用考虑数值超出计算机整数界限的问题）

解法1：（直接大数计算N!）

/** ** @author phinecos* @since 2005-05-27 */ public class test{ private static Stringmultipy(Stringnum1,Stringnum2){ // 大数乘法 Stringresult = " 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 ' ;Stringsum = " 0 " ; for (j = 0 ;j < n1; ++ j){sum = add(sum,num2);}StringBuildertmpSB = 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 ' ;Stringsum = " 0 " ; for (j = 0 ;j < n2; ++ j){sum = add(sum,num1);}StringBuildertmpSB = new StringBuilder(sum); for (j = i;j < len2 - 1 ; ++ j){tmpSB.append( " 0 " );}result = add(result,tmpSB.toString());}} return result;} private static Stringadd(Stringnum1,Stringnum2){Stringresult = "" ; int len1 = num1.length(); int len2 = num2.length(); int nAddOn = 0 ; int i,j,n1,n2,sum;StringBuildersb = 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 Stringfactorial( int n){Stringresult = " 1 " ; for ( int i = n;i >= 2 ; -- i){result = multipy(result,String.valueOf(i));} return result;} private static int countNFactZeroes( int n){Stringresult = 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，即相加，便得到以下算法

等比数列的项数为

log5(N) ，即为循环的次数，故复杂度为 log5(N)

2,题目：请编写一个 C 函数，该函数将给定的一个字符串转换成整数

/* ********************************************************************** */ /* Author:phinecosDate: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:phinecosDate: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 ;}

相关资源：全国计算机等级考试笔试题练习

转载请注明原文地址: https://www.6miu.com/read-5050820.html

Java

最新回复(0)