正负数十进制转二进制 位运算 C语言版
文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
今天在论坛上看到一个负十进制数转二进制的问题，于是小研究了一下，顺便学习位运算。。。
我们知道负数的二进制是由其正数的二进制取反(求反码)再加一(求补码)得到的，例如：
十进制数528的二进制码为：0000001000010000
将其取反(求反码)后的结果：1111110111101111
将反码加一(求补码)后结果：1111110111110000
所以，-528的二进制码为1111110111110000
小说一下概念，然后看一个位运算符,按位与(&) ：0&0=0 , 0&1=0 , 1&0=0 , 1&1=1
我们知道，奇数的二进制最后一位全部为1，而偶数的二进制最后一位全部为0，那么用按位与运算符我们可以很方便地知道一个数是奇数还是偶数，只要让数字 &1 就可以了，因为 奇数&1=1 ，而 偶数&1=0
现在看一段代码，作用是将十进制数转换为二进制数。
#include <stdio.h>
int main()
{
int x,i;
scanf("%d",&x);
for(i=31;i>=0;i--) printf("%d",x>>i&1);
system("pause");
}
重点就在 x>>i&1 啦，每次按照能否被二整除来确定0或者1，然后一位一位的移动，这样处理负数也是可以的，很爽~详细解释太麻烦，自己思考吧，嘎嘎~
碾转相除法求最大公约数不用比较两数大小
文章作者：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;
}
堆排序(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;
}
编译运行，没问题！这点需要注意，否则极易造成溢出。
-
欢迎订阅！
