本文共 6098 字,大约阅读时间需要 20 分钟。
int factorial(int n){ while (n > 1) { return n*func(n-1); }}
当然也可以不用while循环,因为都是n级运算,算法复杂度都为O(n),所以影响不大。
int factorial(int n){ if(n == 0) { return 1; } else { return n*func(n-1); }}
因为要把一个整数颠倒过来。所以得把从低位到高位的顺序分别打印出来,然后乘以相应的倍数,最后相加即可。
#includeint getLen(int num) //计算该数一共有多少位(长度){ int flags = 0; for (num; num >0 ; num/=10) { flags++; } return flags; //返回位数(长度)}int getIndex(int len) //len是数的位数{ int i=0; int res = 1; for (i = 0; i < len ; i++) { res=res*10; } return res; //返回10^i}int main(){ int num,temp,LastNum; printf("please input a num:\n"); scanf("%d",&num); int len = getLen(num); int i=0; for(i = 0; i
算法一:相当于把数组对应位置前后调换,只需要n/2次。
for (i = 0;i < n/2;i++){ t = arr[i]; arr[i] = arr[n-1-i]; arr[n-1-i] = t;}
算法二:
for (i = 0;i < n;i++) b[i] = a[n-i-1];for (i = 0;i < n;i++) a[i]=b[i];
算法一借助辅助空间t ,而算法二借助辅助空间为 b[n]。所以空间复杂度来说,算法一空间复杂度为O(1),算法二空间复杂度为O(n)。
Fib(0) = 0
Fib(1) = 1 Fib(n) = Fib(n-1) + Fib(n-2)F() = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …
int Fibonacci(int n){ if (n <= 1) return n; else return Fibonacci(n - 1) + Fibonacci(n - 2);}
这里,给定规模 n,计算 Fib(n) 所需的时间为计算 Fib(n-1) 的时间和计算 Fib(n-2) 的时间的和。
T(n<=1) = O(1)
T(n) = T(n-1) + T(n-2) + O(1)
fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1)/ \ / \ / \
通过使用递归树的结构描述可知算法复杂度为 O(2n)。
int Fibonacci(int n){ if (n <= 1) return n; else { int[] f = new int[n + 1]; f[0] = 0; f[1] = 1; for (int i = 2; i <= n; i++) { f[i] = f[i - 1] + f[i - 2]; } return f[n]; }}
int Fibonacci(int n){ if (n <= 1) return n; else { int iter1 = 0; int iter2 = 1; int f = 0; for (int i = 2; i <= n; i++) { f = iter1 + iter2; iter1 = iter2; iter2 = f; } return f; }}
方法一(使用联合体):
这里用到了联合体:联合体内成员共享内存,所以所有成员首地址相同。 所以可以通过对较长的成员赋值,通过判断另个一个成员变量的值来判断存放的是高位字节还是低位。union { char c; unsigned short s; }A; A.s = 0x1234; if(A.c == 0x12) //0x12是高位字节 { printf("It's MSB"); // 1 0x34 // 0 0x12 } else { printf("It's LSB"); // 1 0x12 // 0 0x34 }
方法二:(不使用联合)
unsigned int a = 0x12345678; unsigned char i = (unsigned char)a; //截断a if (i == 0x12) { printf("MSB"); } else { printf("LSB"); }
这里用的是桶排序的思想。桶排序虽然速度快,算法简单,但是因为要借助辅助空间,浪费空间,只适合对较少的数据排序。
#includevoid sortage(int arr[],int len){ int i=0; if (arr == NULL || len <= 0) { return; } const int oldestAge = 99; //最大年龄 int timeofAge[oldestAge+1]; //每个年龄次数(辅助内存) //初始化数组 for(i = 0;i <= oldestAge;i++) { timeofAge[i] = 0; } for (i = 0;i < len;i++) //循环读入年龄 { int age = arr[i]; if(age < 0 || age > oldestAge ) { printf("age is not in the range"); } timeofAge[age]++; //每个年龄作为数组的下标,就代表这个年龄的员工有几人 } int index=0; int j=0; //双层循环,外层遍历所有年龄 for (i = 0;i <= oldestAge;i++) { for (j = 0;j < timeofAge[i];j++) //内层循环:出现几次就打印几次 { arr[index] = i; ++index; } }}void main(){ int i=0; int arr[7]={ 22,18,23,22,50,34,19}; sortage(arr,7); for(i = 0;i < 7;i++) { printf("%d ",arr[i]); }}
编写一个函数,作用是把一个char组成的字符串循环右移n个。比如原来是“abcdefghi”如果n=2,移位后应该是“hiabcdefgh” 函数头是这样的:
//pStr是指向以’\0’结尾的字符串的指针
//steps是要求移动的n
void LoopMove ( char * pStr, int steps )
{
//请填充…
}
正确答案:
解析:都是用临时变量来存储,然后通过指针指向来实现改变。解答2更直观。正确解答1:void LoopMove ( char *pStr, int steps ){ int n = strlen( pStr ) - steps; char tmp[MAX_LEN]; strcpy ( tmp, pStr + n ); strcpy ( tmp + steps, pStr); *( tmp + strlen ( pStr ) ) = '\0'; strcpy( pStr, tmp );}正确解答2:void LoopMove ( char *pStr, int steps ){ int n = strlen( pStr ) - steps; char tmp[MAX_LEN]; memcpy( tmp, pStr + n, steps ); memcpy(pStr + steps, pStr, n ); memcpy(pStr, tmp, steps );}
思想:这里采用逆向思维,把字符串从后往前数,依次对每个字符判断是否为空,定义一个变量计数。
#include#include using namespace std;int main(){ string s; while(getline(cin,s)) //c++键盘输入的一种表达 { int n=0,flag=1; for(int i = s.length()-1; i >= 0;--i) { //倒着计算 if(flag && s[i]==' ') { //如果末尾有空格,先清除末尾空格 continue; } else if(s[i]!=' ') { flag = 0; ++n; } else { break; } } cout << n << endl; } return 0;}
删除一个字符串中指定的所有某个字符。
解法一:
思想:找到某字符后把后面的字符串依次往前移动。算法复杂度为O(n^2)。void dele_char(char *str,char s){ char *p = str; char *temp=NULL; while ( *p != '\0' ) { if (*p == s) { temp = p; //找到字符后保存该地址,方便返回继续遍历 while (*p != '\0' ) { *p = *(p+1); p++; } p = temp-1; //返回前一个位置,为了防止该字符连续出现 } p++; } }
方法二
思想:上面方法复杂度是O(n^2),下面用更简单的算法复杂度来实现。这里思想是直接对该字符不予理踩,对不相等的部分重新赋值。void dele_char(char *str,char s){ int i = 0; int j = 0; for (i = 0; i < strlen(a); i++) { if (a[i] != 'f') { a[j] = a[i]; //把不相等的部分进行赋值 j++; } } a[j] = '\0'; //最后一位设置为'\0'
a < b < c : 判断b在a~c之间
static inline int between(__u32 a, __u32 b, __u32 c){ return c - a >= b - a;}
杰发科技2015改错题:
把一个字符串s拷贝到t中,并且把倒叙的字符串s接到t后面。
如: 输入:abc. 打印:abccba#include#include #include void inv_cat(char *s,char *t){ int i,len; len = strlen(s); for (i=0; i
持续更新中。。。。