数字之谜 - 数字中的技巧

kidding33 贡献于2012-06-14

作者 machenyu  创建于2008-08-06 11:15:00   修改者baiaiping  修改于2009-12-09 05:45:00字数8223

文档摘要:数字之谜 - 数字中的技巧
关键词:

 第2章 数字之魅 ——数字中的技巧 代码清单2-1 int Count(BYTE v) { int num = 0; while(v) { if(v % 2 == 1) { num++; } v = v/ 2; } return num; } 代码清单2-2 int Count(BYTE v) { int num = 0; while(v) { num += v & 0x01; v >>= 1; } return num; } 代码清单2-3 int Count(BYTE v) { int num = 0; while(v) { v &= (v-1); 编程之美——微软技术面试心得 num++; } return num; } 代码清单2-4 int Count(BYTE v) { int num = 0; switch (v) { case 0x0: num = 0; break; case 0x1: case 0x2: case 0x4: case 0x8: case 0x10: case 0x20: case 0x40: case 0x80: num = 1; break; case 0x3: case 0x6: case 0xc: case 0x18: case 0x30: case 0x60: case 0xc0: num = 2; break; //... } return num; } 代码清单2-5 /* 预定义的结果表 */ int countTable[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 编程之美——微软技术面试心得 }; int Count(BYTE v)) { //check parameter return countTable[v]; } 代码清单2-6 ret = 0; for(i = 1; i <= N; i++) { j = i; while(j % 5 ==0) { ret++; j /= 5; } } 代码清单2-7 int lowestOne(int N) { int Ret = 0; while(N) { N >>= 1; Ret += N; } return Ret; } 代码清单2-8 Type Find(Type* ID, int N) { Type candidate; int nTimes, i; for(i = nTimes = 0; i < N; i++) { if(nTimes == 0) { candidate = ID[i], nTimes = 1; } else { if(candidate == ID[i]) nTimes++; else nTimes--; } } return candidate; } 编程之美——微软技术面试心得 代码清单2-9 ULONGLONG Count1InAInteger(ULONGLONG n) { ULONGLONG iNum = 0; while(n != 0) { iNum += (n % 10 == 1) ? 1 : 0; n /= 10; } return iNum; } ULONGLONG f(ULONGLONG n) { ULONGLONG iCount = 0; for (ULONGLONG i = 1; i <= n; i++) { iCount += Count1InAInteger(i); } return iCount; } 代码清单2-10 LONGLONG Sum1s(ULONGLONG n) { ULONGLONG iCount = 0; ULONGLONG iFactor = 1; ULONGLONG iLowerNum = 0; ULONGLONG iCurrNum = 0; ULONGLONG iHigherNum = 0; while(n / iFactor != 0) { iLowerNum = n - (n / iFactor) * iFactor; iCurrNum = (n / iFactor) % 10; iHigherNum = n / (iFactor * 10); switch(iCurrNum) { case 0: iCount += iHigherNum * iFactor; break; case 1: iCount += iHigherNum * iFactor + iLowerNum + 1; break; default: iCount += (iHigherNum + 1) * iFactor; break; } 编程之美——微软技术面试心得 iFactor *= 10; } return iCount; } 代码清单2-11 Kbig(S, k): if(k <= 0): return [] // 返回空数组 if(length S <= k): return S (Sa, Sb) = Partition(S) return Kbig(Sa, k).Append(Kbig(Sb, k – length Sa) Partition(S): Sa = [] // 初始化为空数组 Sb = [] // 初始化为空数组 Swap(s[1], S[Random()%length S]) // 随机选择一个数作为分组标准,以 // 避免特殊数据下的算法退化,也可 // 以通过对整个数据进行洗牌预处理 // 实现这个目的 p = S[1] for i in [2: length S]: S[i] > p ? Sa.Append(S[i]) : Sb.Append(S[i]) // 将p加入较小的组,可以避免分组失败,也使分组 // 更均匀,提高效率 length Sa < length Sb ? Sa.Append(p) : Sb.Append(p) return (Sa, Sb) 代码清单2-12 while(Vmax – Vmin > delta) { Vmid = Vmin + (Vmax - Vmin) * 0.5; if(f(arr, N, Vmid) >= K) Vmin = Vmid; else Vmax = Vmid; } 代码清单2-13 if(X > h[0]) { h[0] = X; p = 0; while(p < K) { q = 2 * p + 1; if(q >= K) 编程之美——微软技术面试心得 break; if((q < K – 1) && (h[q + 1] < h[q])) q = q + 1; if(h[q] < h[p]) { t = h[p]; h[p] = h[q]; h[q] = t; p = q; } else break; } } 代码清单2-14 for(sumCount = 0, v = MAXN – 1; v >= 0; v--) { sumCount += count[v]; if(sumCount >= K) break; } return v; 代码清单2-15 BigInt gcd(BigInt x, BigInt y) { if(x < y) return gcd(y, x); if(y == 0) return x; else return gcd(x - y, y); } 代码清单2-16 BigInt gcd(BigInt x, BigInt y) { if(x < y) return gcd(y, x); if(y == 0) return x; else { if(IsEven(x)) { if(IsEven(y)) return (gcd(x >> 1, y >> 1) << 1); else return gcd(x >> 1, y); } else 编程之美——微软技术面试心得 { if(IsEven(y)) return gcd(x, y >> 1); else return gcd(y, x - y); } } } 代码清单2-17 // 初始化 for(i = 0; i < N; i++) BigInt[i].clear(); BigInt[1].push_back(0); int NoUpdate = 0; for(i=1,j=10%N; ; i++,j=(j*10)%N) { bool flag = false; if(BigInt[j].size() == 0) { flag = true; // BigInt[j] = 10^i, (10^i % N = j) BigInt[j].clear(); BigInt[j].push_back(i); } for(k = 1; k < N; k++) { if((BigInt[k].size() > 0) && (i > BigInt[k][BigInt[k].size() - 1]) && (BigInt[(k + j) % N].size() == 0)) { // BigInt[(k + j) % N] = 10^i + BigInt[k] flag = true; BigInt[(k + j) % N] = BigInt[k]; BigInt[(k + j) % N].push_back(i); } } if(flag == false) NoUpdate++; else NoUpdate=0; // 如果经过一个循环节都没能对BigInt进行更新,就是无解,跳出。 // 或者BigInt[0] != NULL,已经找到解,也跳出。 if(NoUpdate == N || BigInt[0].size() > 0) break; } if(BigInt[0].size() == 0) { // M not exist } else { // Find N * M = BigInt[0] } 编程之美——微软技术面试心得 代码清单2-18 int Fibonacci(int n) { if(n <= 0) { return 0; } else if (n == 1) { return 1; } else { return Fibonacci(n - 1) + Fibonacci(n - 2); } } 代码清单2-19 Class Matrix; // 假设我们已经有了实现乘法操作的矩阵类 // 求解m的n次方 Matrix MatrixPow(const Matrix& m, int n) { Matrix result = Matrix::Identity; // 赋初值为单位矩阵 Matrix tmp = m; for(; n; n >>= 1) { if (n & 1) result *= tmp; tmp *= tmp; } } int Fibonacci(int n) { Matrix an = MatrixPow(A, n - 1); // A的值就是上面求解出来的 return F1* an(0, 0) + F0 * an(1, 0); // 返回Fn } 代码清单2-20 (max, min) Search(arr, b, e) { if(e - b <= 1) { if(arr[b] < arr[e]) return (arr[e], arr[b]); else return (arr[b], arr[e]); } (maxL, minL) = Search(arr, b, b + (e - b) / 2); (maxR, minR) = Search(arr, b + (e - b) / 2 + 1, e); if(maxL > maxR) maxV = maxL; 编程之美——微软技术面试心得 else maxV = maxR; if(minL < minR) minV = minL; else minV = minR; return (maxV, minV); } 代码清单2-21 double MinDifference(double arr[], int n) { if(n < 2) { return 0; } double fMinDiff = fabs(arr[0] – arr[1]); for(int i = 0; i < n; ++i) for(int j = i + 1; j <n; ++j) { double tmp = fabs(arr[i] – arr[j]); if(fMinDiff > tmp) { fMinDiff = tmp; } } return fMinDiff; } 代码清单2-22 double MinDifference(double arr[], int n) { if(n < 2) { return 0; } // Sort array arr[] Sort(arr, arr + n); double fMinDiff = arr[1] - arr[0]; for(int i = 2; i < n; ++i) { double tmp = arr[i] - arr[i - 1]; if(fMinDiff > tmp) { fMinDiff = tmp; } } return fMinDiff; } 代码清单2-23:伪代码 编程之美——微软技术面试心得 for(i = 0, j = n - 1; i < j; ) if(arr[i] + arr[j] == Sum) return (i, j); else if(arr[i] + arr[j] < Sum) i++; else j--; return(-1, -1); 代码清单2-24 int MaxSum(int* A, int n) { int maximum = -INF; int sum; for(int i = 0; i < n; i++) { for(int j = i; j < n; j++) { for(int k = i; k <= j; k++) { sum += A[k]; } if(sum > maximum) maximum = sum; } } return maximum; } 代码清单2-25 int MaxSum(int* A, int n) { int maximum = -INF; int sum; for(int i = 0; i < n; i++) { sum = 0; for(int j = i; j < n; j++) { sum += A[j]; if(sum > maximum) maximum = sum; } } return maximum; } 代码清单2-26 int max(int x, int y) // 返回x,y两者中的较大值 { return (x > y) ? x : y; 编程之美——微软技术面试心得 } int MaxSum(int* A, int n) { Start[n - 1] = A[n - 1]; All[n - 1] = A[n - 1]; for(i = n - 2; i >= 0; i--) // 从数组末尾往前遍历,直到数组首 { Start[i] = max(A[i], A[i] + Start[i + 1]); All[i] = max(Start[i], All[i + 1]); } return All[0]; // 遍历完数组,All[0]中存放着结果 } 代码清单2-27 int max(int x, int y) { return (x > y) ? x : y; } // 用于比较x和y的大小,返回x和y中的较大者 int MaxSum(int* A, int n) { // 要做参数检查 nStart = A[n - 1]; nAll = A[n - 1]; for(i = n-2; i >= 0; i--) { nStart = max(A[i], nStart + A[i]); nAll = max(nStart, nAll); } return nAll; } 代码清单2-28 int MaxSum(int* A, int n) { // 要做输入参数检查 nStart = A[n - 1]; nAll = A[n - 1]; for(i = n - 2; i >= 0; i--) { if(nStart < 0) nStart = 0; // 数组全部是负数,如何? nStart += A[i]; if(nStart > nAll) nAll = nStart; } return nAll; } 代码清单2-29 int max(int x, int y) 编程之美——微软技术面试心得 { return (x > y) ? x : y; // 用于比较x和y的大小,返回x和y中的较大者 } // @parameters // A,二维数组 // n,行数 // m,列数 int MaxSum(int* A, int n, int m) { maximum = -INF; for(i_min = 1; i_min <= n; i_min++) for(i_max = i_min; i_max <= n; i_max++) for(j_min = 1; j_min <= m; j_min++) for(j_max = j_min; j_max <= m; j_max++) maximum = max(maximum, Sum(i_min, i_max, j_min, j_max)); return maximum; } 代码清单2-30 // @parameters // A,二维数组 // n,行数 // m,列数 int MaxSum(int* A, int n, int m) { maximum = -INF; for(a = 1; a <= n; a++) for(c = a; c <= n; c++) { Start = BC(a, c, m); All = BC(a, c, m); for(i = m-1; i >= 1; i--) { if(Start < 0) Start = 0; Start += BC(a, c, i); if(Start > All) All = Start; } if(All > maximum) maximum = All; } return maximum; } 代码清单2-31:C#代码 int LIS(int[] array) { 编程之美——微软技术面试心得 int[] LIS = new int[array.Length]; for(int i = 0; i < array.Length; i++) { LIS[i] = 1; // 初始化默认的长度 for(int j = 0; j < i; j++) // 找出前面最长的序列 { if(array[i] > array[j] && LIS[j] + 1 > LIS[i]) { LIS[i] = LIS[j] + 1; } } } return Max(LIS); // 取LIS的最大值 } 代码清单2-32:C#代码 int LIS(int[] array) { // 记录数组中的递增序列信息 int[] MaxV = new int[array.Length + 1]; MaxV[1] = array[0]; // 数组中的第一值,边界值 MaxV[0] = Min(array) - 1; // 数组中最小值,边界值 int[] LIS = new int[array.Length]; // 初始化最长递增序列的信息 for(int i = 0; i < LIS.Length; i++) { LIS[i] = 1; } int nMaxLIS = 1; // 数组最长递增子序列的长度 for(int i = 1; i < array.Length; i++) { // 遍历历史最长递增序列信息 int j; for(j = nMaxLIS; j >= 0; j--) { if(array[i] > MaxV[j]) { LIS[i] = j + 1; break; } } // 如果当前最长序列大于最长递增序列长度,更新最长信息 if(LIS[i] > nMaxLIS) { nMaxLIS = LIS[i]; MaxV[LIS[i]] = array[i]; } 编程之美——微软技术面试心得 else if (MaxV[j] < array[i] && array[i] < MaxV[j + 1]) { MaxV[j + 1] = array[i]; } } return nMaxLIS; } 代码清单2-33 RightShift(int* arr, int N, int K) { while(K--) { int t = arr[N - 1]; for(int i = N - 1; i > 0; i --) arr[i] = arr[i - 1]; arr[0] = t; } } 代码清单2-34 RightShift(int* arr, int N, int K) { K %= N; while(K--) { int t = arr[N - 1]; for(int i = N - 1; i > 0; i --) arr[i] = arr[i - 1]; arr[0] = t; } } 代码清单2-35 Reverse(int* arr, int b, int e) { for(; b < e; b++, e--) { int temp = arr[e]; arr[e] = arr[b]; arr[b] = temp; } } RightShift(int* arr, int N, int k) { K %= N; Reverse(arr, 0, N – K - 1); Reverse(arr, N - K, N - 1); Reverse(arr, 0, N - 1); } 编程之美——微软技术面试心得 代码清单2-36 定义:Heap[i]表示存储从arr中取i个数所能产生的和之集合的堆。 初始化:Heap[0]只有一个元素0。Heap[i],i〉0没有元素。 for(k = 1; k <= 2 * n; k++) { i_max = min(k - 1, n - 1); for(i = i_max; i >= 0; i--) { for each v in Heap[i] insert(v + arr[k], Heap[i + 1]); } } 代码清单2-37 定义:isOK[i][v]表示是否可以找到i个数,使得它们之和等于v 初始化 isOK[0][0] = true; isOK[i][v] = false(i > 0, v > 0) for(k = 1; k <= 2 * n; k++) { for(i = min(k, n); i>= 1; i--) for(v = 1; v <= Sum / 2; v++) if(v >= arr[k] && isOK[i - 1][v – arr[k]]) isOK[i][v] = true; } 代码清单2-38:C#代码 using System; using System.Collections.Generic; using System.Text; namespace FindTheNumber { class Program { static void Main(string[] args) { int [] rg = {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17, 18,19,20,21,22,23,24,25,26,27,28,29,30,31}; for(Int64 i = 1; i < Int64.MaxValue; i++) { int hit = 0; int hit1 = -1; int hit2 = -1; for (int j = 0; (j < rg.Length) && (hit <= 2); j++) { if((i % rg[j]) != 0) { hit++; if(hit == 1) { hit1 = j; 编程之美——微软技术面试心得 } else if (hit == 2) { hit2 = j; } else break; } } if((hit == 2) && (hit1 + 1 == hit2)) { Console.WriteLine("found {0}", i); } } } } } 编程之美——微软技术面试心得

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档