碾转相除法求最大公约数不用比较两数大小
文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
辗转相除，又名欧几里德算法(Euclidean algorithm)，是求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至前300年。它首次出现于欧几里德的《几何原本》中，而在中国则可以追溯至东汉出现的《九章算术》。
以前学碾转相除的时候也没怎么考虑，看到书上说要先比较两个数的大小再碾转相除我就习惯性地先比较大小了，可是今天发现碾转相除法是不用比较两个数的大小的。。。
设我们有两个数m、n
1、用m除以n，得余数r
2、使m=n ，n=r
3、若r=0，则m就是最大公约数；若r不等于0，返回第1步
我们可以看到，如果m>n，那么没说的；如果m<n，在第一次m除以n后，余数恰好为m，这样一交换，最后还会变成m>n的情况。
C语言实现代码为：
#include <stdio.h>
int main()
{
int m, n, r = 1;
scanf("%d%d", &m, &n);
while (r != 0)
{
r = m % n;
m = n;
n = r;
}
printf("%d", m);
return 0;
}
还有一个利用条件运算符写的求最大公约数程序代码
#include<stdio.h>
int main()
{
int m, n;
scanf("%d%d", &m, &n);
while(m > n ? (m = m % n) : (n = n % m));
printf("%d", m + n);
return 0;
}
八皇后问题 回溯递归 C语言版
文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
今天听陈星火老师(火爷)的讲座提到了八皇后问题，正好今天没写的，于是晚上上完课回来就写了一段回溯递归解决八皇后问题的代码，当然也可以解决N皇后问题。运行后得到解为92组。
/* Code by Slyar */
#include <stdio.h>
#include <stdlib.h>
#define max 8
int queen[max], sum=0; /* max为棋盘最大坐标 */
void show() /* 输出所有皇后的坐标 */
{
int i;
for(i = 0; i < max; i++)
{
printf("(%d,%d) ", i, queen[i]);
}
printf("\n");
sum++;
}
int check(int n) /* 检查当前列能否放置皇后 */
{
int i;
for(i = 0; i < n; i++) /* 检查横排和对角线上是否可以放置皇后 */
{
if(queen[i] == queen[n] || abs(queen[i] - queen[n]) == (n - i))
{
return 1;
}
}
return 0;
}
void put(int n) /* 回溯尝试皇后位置,n为横坐标 */
{
int i;
for(i = 0; i < max; i++)
{
queen[n] = i; /* 将皇后摆到当前循环到的位置 */
if(!check(n))
{
if(n == max - 1)
{
show(); /* 如果全部摆好，则输出所有皇后的坐标 */
}
else
{
put(n + 1); /* 否则继续摆放下一个皇后 */
}
}
}
}
int main()
{
put(0); /* 从横坐标为0开始依次尝试 */
printf("%d", sum);
system("pause");
return 0;
}
C语言运算符优先级 详细列表
文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
恩，问这个问题的人太多了，懒得继续回答，直接贴上来自己看。。。
|
优先级 |
运算符 |
名称或含义 |
使用形式 |
结合方向 |
说明 |
|
1 |
[] |
数组下标 |
数组名[常量表达式] |
左到右 |
|
|
() |
圆括号 |
（表达式）/函数名(形参表) |
|||
|
. |
成员选择（对象） |
对象.成员名 |
|||
|
-> |
成员选择（指针） |
对象指针->成员名 |
|||
|
2 |
- |
负号运算符 |
-表达式 |
右到左 |
单目运算符 |
|
(类型) |
强制类型转换 |
(数据类型)表达式 |
|||
|
++ |
自增运算符 |
++变量名/变量名++ |
单目运算符 |
||
|
-- |
自减运算符 |
--变量名/变量名-- |
单目运算符 |
||
|
* |
取值运算符 |
*指针变量 |
单目运算符 |
||
|
& |
取地址运算符 |
&变量名 |
单目运算符 |
||
|
! |
逻辑非运算符 |
!表达式 |
单目运算符 |
||
|
~ |
按位取反运算符 |
~表达式 |
单目运算符 |
||
|
sizeof |
长度运算符 |
sizeof(表达式) |
|||
|
3 |
/ |
除 |
表达式/表达式 |
左到右 |
双目运算符 |
|
* |
乘 |
表达式*表达式 |
双目运算符 |
||
|
% |
余数（取模） |
整型表达式/整型表达式 |
双目运算符 |
||
|
4 |
+ |
加 |
表达式+表达式 |
左到右 |
双目运算符 |
|
- |
减 |
表达式-表达式 |
双目运算符 |
||
|
5 |
<< |
左移 |
变量<<表达式 |
左到右 |
双目运算符 |
|
>> |
右移 |
变量>>表达式 |
双目运算符 |
||
|
6 |
> |
大于 |
表达式>表达式 |
左到右 |
双目运算符 |
|
>= |
大于等于 |
表达式>=表达式 |
双目运算符 |
||
|
< |
小于 |
表达式<表达式 |
双目运算符 |
||
|
<= |
小于等于 |
表达式<=表达式 |
双目运算符 |
||
|
7 |
== |
等于 |
表达式==表达式 |
左到右 |
双目运算符 |
|
!= |
不等于 |
表达式!= 表达式 |
双目运算符 |
||
|
8 |
& |
按位与 |
表达式&表达式 |
左到右 |
双目运算符 |
|
9 |
^ |
按位异或 |
表达式^表达式 |
左到右 |
双目运算符 |
|
10 |
| |
按位或 |
表达式|表达式 |
左到右 |
双目运算符 |
|
11 |
&& |
逻辑与 |
表达式&&表达式 |
左到右 |
双目运算符 |
|
12 |
|| |
逻辑或 |
表达式||表达式 |
左到右 |
双目运算符 |
|
13 |
?: |
条件运算符 |
表达式1? 表达式2: 表达式3 |
右到左 |
三目运算符 |
|
14 |
= |
赋值运算符 |
变量=表达式 |
右到左 |
|
|
/= |
除后赋值 |
变量/=表达式 |
|||
|
*= |
乘后赋值 |
变量*=表达式 |
|||
|
%= |
取模后赋值 |
变量%=表达式 |
|||
|
+= |
加后赋值 |
变量+=表达式 |
|||
|
-= |
减后赋值 |
变量-=表达式 |
|||
|
<<= |
左移后赋值 |
变量<<=表达式 |
|||
|
>>= |
右移后赋值 |
变量>>=表达式 |
|||
|
&= |
按位与后赋值 |
变量&=表达式 |
|||
|
^= |
按位异或后赋值 |
变量^=表达式 |
|||
|
|= |
按位或后赋值 |
变量|=表达式 |
|||
|
15 |
, |
逗号运算符 |
表达式,表达式,… |
左到右 |
从左向右顺序运算 |
说明：
同一优先级的运算符，运算次序由结合方向所决定。
简单记就是：！ > 算术运算符 > 关系运算符 > && > || > 赋值运算符
堆排序(Heap Sort) 算法实现 C语言版
文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
n个关键字序列Kl，K2，…，Kn称为堆(Heap)，当且仅当该序列满足如下性质(简称为堆性质)：
ki≤K2i且ki≤K2i+1 或 Ki≥K2i且ki≥K2i+1(1≤i≤ n)
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 (即如果按照线性存储该树，可得到一个不下降序列或不上升序列)
SLYAR整理了一下算法，用C语言实现，带注释。
void sift(int a[],int i,int n) /* i为根节点,n为节点总数 */
{
int child,tmp;
for (tmp=a[i];n>2*i;i=child)
{
child=2*i; /* i的左孩子为2*i,右孩子为2*i+1 */
if (child!=n-1&&a[child+1]>a[child]) /* 让child指向孩子中较大的一个 */
{
child++;
}
if (tmp<a[child]) /* 如果孩子节点大 */
{
a[i]=a[child]; /* 交换孩子节点和根节点 */
}
else break;
}
a[i]=tmp; /* 将根放在合适位置 */
}
void heapsort(int a[],int n) /* 对a[1...n]进行排序 */
{
int i,tmp;
for (i=n/2;i>=0;i--) /* 建立初始堆 */
{
sift(a,i,n);
}
for (i=n-1;i>0;i--) /* 进行n-1趟排序 */
{
tmp=a[0]; /* 交换堆顶元素和最后一个元素 */
a[0]=a[i];
a[i]=tmp;
sift(a,0,i); /* 将a[1..n-1]重建为堆 */
}
}
计算程序运行时间 C语言 clock()函数版
文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
自己没事可以看看程序的运行时间，第一个想到的还是以前会的clock() ，先把代码扔这。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
clock_t begin, end;
double cost;
begin = clock();
/* 程序代码 */
end = clock();
cost = (double)(end - begin) / CLOCKS_PER_SEC;
printf("%lf seconds\n", cost);
system("pause");
return 0;
}
这个函数返回开启进程和调用clock()之间的的CPU时钟计时单元(clock tick)数，在MSDN中称之为挂钟时间(wal-clock)，每过千分之一秒(1毫秒)，调用clock()函数返回的值就加1。
但是是我感觉这段程序有两个问题，很不爽。第一是精度，只能精确到1ms，低于1ms的程序全部输出0ms，因为WinNT的时间精度最小是1ms；第二是准确度，printf()的速度太快了，基本上和clock()的速度一样，所以误差很大很大。。。
不晓得在Win下怎么才能提高计算精度。。。
输入缓冲区与C语言的流问题
文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
今天发现一个问题，已经造成了溢出，需要用到传说中的fflush(stdin);来解决。先看下面的代码：
#include <stdio.h>
int main()
{
char s[10],s1[10],s2[10],s3[10];
scanf("%s",&s);
printf("%s\n",s);
scanf("%s%s%s",&s1,&s2,&s3);
printf("%s %s %s\n",s1,s2,s3);
system("pause");
return 0;
}
程序想达到这样一个目的：两次都输入Slyar is good!，第一次输出Slyar，第二次输出Slyar is good!。但是结果却不是我们期望看到的，而是：
Slyar is good!
Slyar
Slyar is good!
is good! Slyar
其中蓝色是我输入的部分，而红色是程序输出的结果，可以看到第二次程序没有输出Slyar is good!而是输出了is good! Slyar，我们来分析一下。
当我们输入Slyar is good!后，系统会把第一个空白当成结束，也就是输出Slyar，这没错。然后紧接着我们再次输入Slyar is good!，按照一般思维，应该是Slyar给了S1,is给了S2，good!给了S3，但是。。。
你看到的is good! Slyar中的is good!其实是第一次输入Slyar is good!后余留在缓冲区里的那部分！也就是说，当第一次系统截断Slyar以后，剩下的部分就留在了缓冲区，当你第二次输入后，系统就把缓冲区里的is good!分配给了S1和S2。这样，只有第三次输入的Slyar被分配给了S3，所以当我们打印S1、S2、S3时，会出现is good! Slyar
那么怎么解决这个问题呢？这就要用到fflush(stdin);了：stdin是默认的输入流文件，对应输入缓冲，而fflush(stdin);就可以清空整个输入缓冲区，本例中即把缓冲区内的is good!刷掉。所以，我们的代码应该这样写：
#include <stdio.h>
int main()
{
char s[10],s1[10],s2[10],s3[10];
scanf("%s",&s);
printf("%s\n",s);
fflush(stdin);
scanf("%s%s%s",&s1,&s2,&s3);
printf("%s %s %s\n",s1,s2,s3);
system("pause");
return 0;
}
编译运行，没问题！这点需要注意，否则极易造成溢出。
-
欢迎订阅！
