2011年12月23日
#
//冒泡排序 （升序）
//冒泡排序中间过程
#include <stdio.h>
#include <stdlib.h>
int main()
{
int i,j,k;
int n;
int t;
int a[10];
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<n;i++)
{
for(j=1;j<n-i+1;j++)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
for(j=1;j<=n;j++)
printf("%d ",a[j]);
printf("\n");
}
system("pause");
return 0;
}
//析 ：小数左移；大数右移
//该循环中i执行了n-1次，因为当倒数第二个数确定时，第一个数自然就确定了
2011年12月18日
#
一、C++中不能使用random()函数
random函数不是ANSI C标准，不能在gcc,vc等编译器下编译通过。但在C语言中int random(num)可以这样使用，它返回的是0至num-1的一个随机数。 可改用C++下的rand函数来实现。
1、C++标准函数库提供一随机数生成器rand，返回0－RAND_MAX之间均匀分布的伪随机整数。 RAND_MAX必须至少为32767。rand()函数不接受参数，默认以1为种子（即起始值）。 随机数生成器总是以相同的种子开始，所以形成的伪随机数列也相同，失去了随机意义。（但这样便于程序调试）
2、C++中另一函数srand（），可以指定不同的数（无符号整数变元）为种子。但是如果种子相同，伪随机数列也相同。一个办法是让用户输入种子，但是仍然不理想。
3、 比较理想的是用变化的数，比如时间来作为随机数生成器的种子。 time的值每时每刻都不同。所以种子不同，所以，产生的随机数也不同。
// C++随机函数（VC program）
#include <stdio.h>
#include <iostream>
#include <time.h>
using namespace std;
#define MAX 100
int main(int argc, char* argv[])
{
srand( (unsigned)time( NULL ) );//srand()函数产生一个以当前时间开始的随机种子.应该放在for等循环语句前面 不然要很长时间等待
for (int i=0;i<10;i++)
cout<<rand()%MAX<<endl;//MAX为最大值，其随机域为0~MAX-1
return 0;
}
二、rand()的用法
rand()不需要参数，它会返回一个从0到最大随机数的任意整数，最大随机数的大小通常是固定的一个大整数。
/* maximum value returned by "rand" function
*/
#define RAND_MAX 0x7fffu
这个是bcc55中的定义，说明这个整数的最大数是0x7fffu，u代表unicode编码。
这样，如果你要产生0~10的10个整数，可以表达为：
int N = rand() % 11;
这样，N的值就是一个0~10的随机数，如果要产生1~10，则是这样：
int N = 1 + rand() % 10;
总结来说，可以表示为：
a + rand() % n
其中的a是起始值，n是整数的范围。
a + rand() % (b-a+1) 就表示 ａ～ｂ之间的一个随机数
若要0~1的小数，则可以先取得0~10的整数，然后均除以10即可得到随机到十分位的10个随机小数，若要得到随机到百分位的随机小数，则需要先得到0~100的10个整数，然后均除以100，其它情况依
此类推。
通常rand()产生的随机数在每次运行的时候都是与上一次相同的，这是有意这样设计的，是为了便于程序的调试。若要产生每次不同的随机数，可以使用srand( seed )函数进行随机化，随着seed的不同，就能够产生不同的随机数。
如大家所说，还可以包含time.h头文件，然后使用srand(time(0))来使用当前时间使随机数发生器随机化，这样就可以保证每两次运行时可以得到不同的随机数序列(只要两次运行的间隔超过1秒)。
2011年12月17日
#
首先这是一个控制台程序。
包含 #include<stdilib.h>头文件。
system("color 02");是表示黑背景绿色字.
颜色属性由两个十六进制数字指定 -- 第一个为背景，第二个则为前景。每个数字可以为以下任何值之一:
0 = 黑色 8 = 灰色
1 = 蓝色 9 = 淡蓝色
2 = 绿色 A = 淡绿色
3 = 湖蓝色 B = 淡浅绿色
4 = 红色 C = 淡红色
5 = 紫色 D = 淡紫色
6 = 黄色 E = 淡黄色
7 = 白色 F = 亮白色
求解算法的时间复杂度的具体步骤是：
⑴ 找出算法中的基本语句；
算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
⑵ 计算基本语句的执行次数的数量级；
只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
⑶ 用大Ο记号表示算法的时间性能。
将基本语句执行次数的数量级放入大Ο记号中。
如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：
for (i=1; i<=n; i++)
x++;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
x++;
第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。
常见的算法时间复杂度由小到大依次为：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者是有效算法，把这类问题称为P类问题，而把后者称为NP问题。
这只能基本的计算时间复杂度，具体的运行还会与硬件有关。
上面的这部分内容是比较可靠的，理解的时候，可以参看着下面的这部分内容。
在计算算法时间复杂度时有以下几个简单的程序分析法则:
1.对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间
2.对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下"求和法则"
求和法则:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))
特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n))
3.对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间
4.对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则"
乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1*T2=O(f(n)*g(n))
5.对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度
另外还有以下2个运算法则:
(1) 若g(n)=O(f(n)),则O(f(n))+ O(g(n))= O(f(n))
(2) O(Cf(n)) = O(f(n)),其中C是一个正常数
可以用以上法则对下面程序段进行简单分析
①for (i=0; i<n; i++)
② for (j=0; j<n; j++)
{
③ c[i][j] = 0;
④ for (k=0; k<n; k++)
⑤ c[i][j]= c[i][j]+ a[i][k]* b[k][j];/ * T5(n) = O(1) */
}
第①条与②③④⑤是循环嵌套T1(n)*T2(n)* (T3(n)+ T4(n)* T5(n))= O(n*n*n)即为整个算法的时间复杂度
O(1)<O(log2n)<O(n)<O(n log2 n)<O(n^2)<O(n^3)<O(2^n)
#include <iostream>
#include <sys/timeb.h>
#define N 100
using namespace std;
int board[N];
int n,sum;
void init()
{ for(int i = 1; i <= n; i++)
board[i] = 0;
}
void display()
{ int i,j;
cout<<"No."<<sum<<endl;
for(i = 1; i <= n; i++)
{ for(j = 1; j <= n; j++)
if(board[i] == j)
cout<<"Q ";
else
cout<<"X ";
cout<<endl;
}
cout<<endl;
}
bool canPut(int k)
{ for(int i = 1; i < k; i++)
if((abs(k - i) == abs(board[k] - board[i])) || board[i] == board[k])
return false;//1.是否在同一斜线;2.是否位于同一列
return true;
}
void Backtrack()
{ board[1] = 0;
int k = 1;
while(k > 0)
{ board[k]++;
while((board[k] <= n) && !(canPut(k)))
board[k] += 1;
if(board[k] <= n)
if(k == n)
{ sum++;
display();
}
else
{ k++;
board[k] = 0;
}
else k--;
}
}
int main()
{ timeb t1,t2;
long kk;
cout<<"输入皇后个数:";
while(cin>>n)
{ init();
sum = 0;
ftime(&t1);
Backtrack();
ftime(&t2);
cout<<"总共排列方式为:"<<sum<<endl;
kk = (t2.time-t1.time)*1000 + t2.millitm-t1.millitm;
cout<<"本次回溯耗时:"<<kk<<"毫秒"<<endl;
system("PAUSE");
cout<<"输入皇后个数:";
}
return 0;
}
STL，为什么你必须掌握
对于程序员来说，数据结构是必修的一门课。从查找到排序，从链表到二叉树，几乎所有的算法和原理都需要理解，理解不了也要死记硬背下来。幸运的是这些理论都已经比较成熟，算法也基本固定下来，不需要你再去花费心思去考虑其算法原理，也不用再去验证其准确性。不过，等你开始应用计算机语言来工作的时候，你会发现，面对不同的需求你需要一次又一次去用代码重复实现这些已经成熟的算法，而且会一次又一次陷入一些由于自己疏忽而产生的bug中。这时，你想找一种工具，已经帮你实现这些功能，你想怎么用就怎么用，同时不影响性能。你需要的就是STL, 标准模板库！
西方有句谚语：不要重复发明轮子！
STL几乎封装了所有的数据结构中的算法，从链表到队列，从向量到堆栈，对hash到二叉树，从搜索到排序，从增加到删除......可以说，如果你理解了STL，你会发现你已不用拘泥于算法本身，从而站在巨人的肩膀上去考虑更高级的应用。
2011年12月14日
#
#include <iostream>
#include <algorithm>
using namespace std;
// preorder: 1 2 4 7 3 5 8 9 6
// inorder: 4 7 2 1 8 5 9 3 6
//postorder: 7 4 2 8 9 5 6 3 1
int preorder[1005];
int inorder[1005];
void dfs(int pre,int in,int size,bool flag)
{
int i;
if(size==1) //如果有左子树或右子树，就直接输出
{
printf("%d ",preorder[pre]); //不是根节点，所以是空格
return ;
}
if(size<=0) //没有左子树或右子树，则返回上层，遍历右子树或者根
return ;
for(i=0;preorder[pre]!=inorder[in+i];i++);//查找根节点在中序中的位置
dfs(pre+1,in,i,false); //左子树的遍历
dfs(pre+i+1,in+i+1,size-i-1,false); //右子树的遍历
if(flag) //输出根节点
printf("%d\n",preorder[pre]); //整个树的根节点
else
printf("%d ",preorder[pre]); //一般的根节点
}
int main()
{
int n,i;
while(cin>>n)
{
for(i=1;i<=n;i++)
scanf("%d",&preorder[i]);
for(i=1;i<=n;i++)
scanf("%d",&inorder[i]);
dfs(1,1,n,true);
}
return 0;
}如果知道后序遍历和中序遍历，输出先序遍历也是这样，关键是把左子树和右子树分割好
2011年12月10日
#
时间复杂度
冒泡排序： O(n^2)
快速排序： O(nlogn底数为2)
冒泡排序 ：
排序时，最大的元素会如同气泡一样移至右端；
方法：利用比较相邻元素的方法，将大的元素交换移至右端，知道达到恰当的位置
(以向右看齐的原则) 比较次数
排序前: 95 27 90 49 80 58 6 9 18 50 9
1. 27 90 49 80 58 6 9 18 50 [95] 8
2. 27 49 80 58 6 9 18 50 [90 95] 7
3. 27 49 58 6 9 18 50 [80 90 95] 6
4. 27 49 6 9 18 50 [58 80 90 95] 5
5. 27 6 9 18 [49 50 58 80 90 95] 4
6. 6 9 18 [27 49 50 58 80 90 95] 3
(小的下沉,大的上浮)
exit() 结束当前进程/当前程序/，在整个程序中，只要调用 exit ，就结束
return() 是当前函数返回，当然如果是在主函数main, 自然也就结束当前进程了，如果不是，那就是退回上一层调用。在多个进程时.如果有时要检测上进程是否正常退出的.就要用到上个进程的返回值..
exit(1)表示进程正常退出. 返回 1;
exit(0)表示进程非正常退出. 返回 0.
进程环境与进程控制(1): 进程的开始与终止
1. 进程的开始:
C程序是从main函数开始执行, 原型如下:
int main(int argc, char *argv[]);
通常main的返回值是int型, 正确返回0.
如果main的返回值为void或者无, 某些编译器会给出警告, 此时main的返回值通常是0.
关于main的命令行参数不做过多解释, 以下面的程序展示一下:
＃i nclude <stdio.h>
int main(int argc, char *argv[])
{
int i;
for (i = 0; i < argc; i++)
printf("argv[%d]: %s\n", i, argv[i]);
return 0;
}
2. 进程终止:
C程序的终止分为两种: 正常终止和异常终止.
正常终止分为: return, exit, _exit, _Exit, pthreade_exit
异常中指分为: abort, SIGNAL, 线程响应取消
主要说一下正常终止的前4种, 即exit系列函数.
＃i nclude <stdlib.h> /* ISO C */
void exit(int status);
void _Exit(int status);
＃i nclude <unistd.h> /* POSIX */
void _exit(int status);
以上3个函数的区别是:
exit()(或return 0)会调用终止处理程序和用户空间的标准I/O清理程序(如fclose), _exit和_Exit不调用而直接由内核接管进行清
理.
因此, 在main函数中exit(0)等价于return 0.
3. atexit终止处理程序:
ISO C规定, 一个进程最对可登记32个终止处理函数, 这些函数由exit按登记相反的顺序自动调用. 如果同一函数登记多次, 也会被
调用多次.
原型如下:
＃i nclude <stdlib.h>
int atexit(void (*func)(void));
其中参数是一个函数指针, 指向终止处理函数, 该函数无参无返回值.
以下面的程序为例:
＃i nclude <stdlib.h>
static void myexit1()
{
printf("first exit handler\n");
}
static void myexit2()
{
printf("second exit handler\n");
}
int main()
{
if (atexit(my_exit2) != 0)
printf("can't register my_exit2\n");
if (atexit(my_exit1) != 0)
printf("can't register my_exit1\n");
if (atexit(my_exit1) != 0)
printf("can't register my_exit1\n");
printf("main is done\n");
return 0;
}
运行结果:
$ ./a.out
main is done
first exit handler
first exit handler
second exit handler运行结果:
$./a.out arg1 arg2 arg3
argv[0]: ./a.out
argv[1]: arg1
argv[2]: arg2
argv[3]: arg3
2011年12月9日
#
例：70 73 69 23 93 18 11 68
i j
快速排序
1. 用最后一个数和这组数（从头）开始比较大小，
若这个数小于数组比较的这个数，则交换这两个数的位置
即j与i比较大小；
for (int i=0;i<10;i++)
for(int j=9;j>=0;j--)
排序1：68 73 69 23 93 18 11 70
i i+1 j
结 果：68 70 69 23 93 18 11 73
O（3）
排序2：68 70 69 23 93 18 11 73
i i+1 i+2 i+3 i+4 j
结果： 68 70 69 23 73 18 11 93
O（6）
排序3：68 70 69 23 73 18 11 93 //确定93为最大的数
i i+1 i+2 i+3 i+4 i+5 i+6 j
//从这一步可知，下一个数由j+1与前数组注意比较
结果： 68 70 69 23 73 18 11 93
// 意味着开始j的第二重循环
O（7）
排序4：68 70 69 23 73 18 11 93
i j-1 j
结果： 11 70 69 23 73 18 68 93
O（2）
排序5：11 70 69 23 73 18 68 93
i i+1 j-1 j
结果: 11 68 69 23 73 18 70 93
O（3）
排序6：11 68 69 23 73 18 70 93
i i+1 i+2 i+3 i+4 j-1 j
结果： 11 68 69 23 70 18 73 93
O（6）
排序7： 11 68 69 23 70 18 73 93
i i+1 j-2 j-1 j
结果： 11 18 69 23 70 68 73 93
O（3）
排序8：11 18 69 23 70 68 73 93
i i+1 i+2 j-2 j-1 j
结果： 11 18 68 23 70 69 73 93
O（4）
排序9： 11 18 68 23 70 69 73 93
i i+1 i+2 i+3 i+4 j-2 j-1 j
结果： 11 18 68 23 69 70 73 93
O（6）
排序10：11 18 68 23 69 70 73 93
i i+1 i+2 i+3 j-3 j-2 j-1 j
结果: 11 18 68 23 69 70 73 93
O（4）
排序11：11 18 68 23 69 70 73 93
i i+1 i+2 j-4 j-3 j-2 j-1 j
结果： 11 18 23 68 69 70 73 93
O（4）
预计时间复杂度：O(n)=O（48）
最大是多少？