class Program { static void Main( string[] args) { // int[] arr = new int[] { 3, 1, 6, 9, 0 }; // ShellSort3(arr); // for (int i = 0; i < arr.Length; i++) // { // Console.WriteLine(arr[i]); // } for ( int i = 0; i < 90; i++) { Console.WriteLine(Fn2(i)); } Console.WriteLine(Fn2( 1000000000)); // string src = "I am zhang张英ying"; // int result = IndexOfString(src,"a",0); // Console.WriteLine(result); // Console.WriteLine(src); Console.ReadKey(); } public static void InsertionSort( int[] arr) { for ( int i = 1; i < arr.Length; i++) { int t = arr[i]; int j = i; while ((j > 0) && (arr[j - 1] > t)) { arr[j] = arr[j - 1]; // 交换顺序 --j; } arr[j] = t; } } public static void BubbleSort( int[] arr) { int i, j, temp; bool done = false; j = 1; while ((j < arr.Length) && (!done)) // 判断长度 { done = true; for (i = 0; i < arr.Length - j; i++) { if (arr[i] > arr[i + 1]) { done = false; temp = arr[i]; arr[i] = arr[i + 1]; // 交换数据 arr[i + 1] = temp; } } j++; } } public static void TwowayBubbleSort( int[] arr) { bool done = false; int right = arr.Length - 1; int left = 0; do { done = true; for ( int k = left; k < right; k++) { if (arr[k] > arr[k + 1]) { done = false; Swap(arr, k, k + 1); } } right--; if (done) { break; } else { done = true; } for ( int k = right; k > left; k--) { if (arr[k] < arr[k - 1]) { done = false; Swap(arr, k, k - 1); } } left++; } while ((left < right) && (!done)); } public static void ShellSort( int[] arr) { var steps = new int[] { 9, 5, 3, 1}; for ( int i = 0; i < steps.Length; i++) { int k = steps[i]; for( int j=k;j<arr.Length;j++) { if(arr[j]<arr[j-k]) Swap(arr,j,j-k); } } } public static void ShellSort2( int[] arr, int count) { var step = new int[] { 1}; int iTemp; int k, s, w; for ( int i = 0; i < 1; i++) { k = step[i]; s = -k; for ( int j = k; j < count; j++) { iTemp = arr[j]; w = j - k; // 求上step个元素的下标 if (s == 0) { s = -k; s++; arr[s] = iTemp; } while ((w >= 0) && (w <= count) && (iTemp < arr[w])) { arr[w + k] = arr[w]; w = w - k; } arr[w + k] = iTemp; } } } public static void ShellSort3( int[] arr) { int inc; for (inc = 1; inc <= arr.Length/ 9; inc = 3*inc + 1) ; for (; inc > 0; inc /= 3) { for ( int i = inc + 1; i <= arr.Length; i += inc) { int t = arr[i - 1]; int j = i; while ((j > inc) && (arr[j - inc - 1] > t)) { arr[j - 1] = arr[j - inc - 1]; j -= inc; } arr[j - 1] = t; } } } public static void QuickSort( int[] arr, int start, int end) { if (start >= end) return; if ( 1 == end - start) // 可以考虑当end - start小于某个值时采用插入排序 { if (arr[end] >= arr[start]) return; else { Swap(arr,start,end); } } int i = start- 1; int j = end+ 1; int middle = arr[ new Random().Next(start,end)]; // arr[(start + end)/2]; while ( true) { while (arr[++i] < middle && i < end) ; while (arr[--j] > middle && j > start) ; if (i >= j) break; Swap(arr, i,j); } QuickSort(arr, start, i- 1); QuickSort(arr, j + 1, end); } public static void QuickSortNoRecursion( int[] arr, int start, int end) { var dataRanges = new Stack< int[]>(); dataRanges.Push( new int[] { start, end }); while (dataRanges.Count> 0) { int[] data = dataRanges.Pop(); InnerQuickSortNoRecursion(arr, data[ 0], data[ 1], dataRanges); } } private static void InnerQuickSortNoRecursion( int[] arr, int left, int right, Stack< int[]> dataRanges) { if (left >= right) return; if ( 1 == right - left) // 可以考虑当end - start小于某个值时采用插入排序 { if (arr[right] >= arr[left]) return; else { Swap(arr, left, right); } } int i = left - 1; int j = right + 1; int middle = arr[ new Random().Next(left, right)]; // arr[(start + end)/2]; while ( true) { while (arr[++i] < middle && i < right) ; while (arr[--j] > middle && j > left) ; if (i >= j) break; Swap(arr, i, j); } dataRanges.Push( new int[]{ left, i - 1}); dataRanges.Push( new int[]{j + 1, right}); } private static void Swap( int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static string RevertString( string src) { var result = new char[src.Length]; for( int i= 0;i<src.Length/ 2;i++) { result[i] = src[src.Length - i - 1]; result[src.Length - i - 1] = src[i]; } if (src.Length % 2 == 1) { result[src.Length/ 2 + 1] = src[src.Length/ 2 + 1]; } return string.Concat(result); } public static string RevertString2( string src) { char tmp; unsafe { fixed ( char* ps = src) { for ( int i = 0; i < src.Length / 2; i++) { tmp = ps[i]; ps[i] = ps[src.Length - i - 1]; ps[src.Length - i - 1] = tmp; } } } return src; } public static int IndexOfString( string main, string sub, int pos) { var nextPosition = GetNextPosition(sub); int i=pos, j= 0; while(i<main.Length && j<sub.Length) { if (j==- 1||main[i] == sub[j]) { i++; j++; } else { j = nextPosition[j]; } } if (j == sub.Length) { return i - sub.Length; } else { return - 1; } } private static Dictionary< int, int> GetNextPosition( string sub) { int i = 0, j = - 1; var result = new Dictionary< int, int>(); result.Add( 0,- 1); while(i<sub.Length) { if(j==- 1||sub[i]==sub[j]) { i++; j++; result.Add(i,j); } else { result.Add(j,j); } } return result; } public static long Fn( int n) { if ( 3 < n) { if ( 0 == n% 2) { long t1 = Fn(n/ 2); long t2 = Fn(n/ 2 - 1); return t1*t1 + t2*t2; } else { long t1 = Fn(n/ 2); long t2 = Fn(n/ 2 - 1); return 2*t1*t2 + t1*t1; } } if ( 3 == n) return 3; if ( 2 == n) return 2; if ( 1 == n) return 1; return - 1; } /// <summary> /// 基本原理为: /// n为偶数时f(n)=f(n/2)*f(n/2)+f(n-1)*f(n-1); /// n为基数时f(n)=f(n/2+1)*f(n/2)+f(n/2)*f(n/2-1); /// </summary> /// <param name="n"></param> /// <returns></returns> public static long Fn2( int n) { if ( 1 < n) { var steps = new Stack< int>(); while (n > 2) { steps.Push(n); n /= 2; } long r1 = 2, r2 = 3; while (steps.Count > 0) { int tmp = steps.Pop(); if ( 3 < tmp) { long tr1; long tr2; if ( 0 == tmp% 2) { tr1 = 2*r1*r1 + r2*r2 - 2*r1*r2; tr2 = 2*r1*r2 - r1*r1; r1 = tr1; r2 = tr2; } else { tr1 = 2*r1*r2 - r1*r1; tr2 = r1*r1 + r2*r2; r1 = tr1; r2 = tr2; } } else { r1 = 3; r2 = 5; } } return r1; } if ( 1 == n) return 1; return - 1; } }