Oct
22
一切都是从，那道蚂蚁题，开始的
那题中的蚂蚁有20只，爬在长的木棒一根
左边蚂蚁10只向右爬
右边蚂蚁10只向左爬
蚂蚁爬的速度都相同
一碰头各自原速调头
然后就问，这些个蚂蚁，要碰多少次头才会从木棒上都掉下去
一说起这个问题，可能很多人有看过编程之美4.7 蚂蚁爬杆的问题：有一根27厘米长的细长木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置 处各有一只蚂蚁。木杆很细，不能同时通过2只蚂蚁。开始时候，蚂蚁的头朝左还是朝右是任意的，他们只会朝前走或者掉头，但是不会后退。当任意2只蚂蚁碰头后时，2只蚂蚁会同时掉转头朝反方向走。架设蚂蚁每秒钟可以走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最短时间和最长时间。
留一些空间不剧透，有兴趣的同学可以先想想然后再往下看。
那题中的蚂蚁有20只，爬在长的木棒一根
左边蚂蚁10只向右爬
右边蚂蚁10只向左爬
蚂蚁爬的速度都相同
一碰头各自原速调头
然后就问，这些个蚂蚁，要碰多少次头才会从木棒上都掉下去
一说起这个问题，可能很多人有看过编程之美4.7 蚂蚁爬杆的问题：有一根27厘米长的细长木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置 处各有一只蚂蚁。木杆很细，不能同时通过2只蚂蚁。开始时候，蚂蚁的头朝左还是朝右是任意的，他们只会朝前走或者掉头，但是不会后退。当任意2只蚂蚁碰头后时，2只蚂蚁会同时掉转头朝反方向走。架设蚂蚁每秒钟可以走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最短时间和最长时间。
留一些空间不剧透，有兴趣的同学可以先想想然后再往下看。
Sep
30
看了下百度百科对UTF-8的说明，随手写的，基本能用。
比较诡异的是本来UTF8getchar想用strncpy的，但是这个函数有坑....
比较诡异的是本来UTF8getchar想用strncpy的，但是这个函数有坑....
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define alloc(type, size) ((type *)malloc(sizeof(type) * size))
struct UTF8char
{
unsigned short length;
char data[7];
};
unsigned UTF8getcharlen(const char *s)
{
unsigned char t = (unsigned char) s[0];
if (t < 0x80) //0xxx xxxx
return 1;
else if (t < 0xe0) //110x xxxx
return 2;
else if (t < 0xf0) //1110 xxxx
return 3;
else if (t < 0xf8) //1111 0xxx
return 4;
else if (t < 0xfc) //1111 10xx
return 5;
else if (t < 0xfe) //1111 110x
return 6;
else //0xff
return 1;
}
int UTF8getchar(UTF8char *c, const char *s)
{
int i;
c->length = UTF8getcharlen(s);
for (i = 0; i < c->length && s[i] != 0; i++)
c->data[i] = s[i];
c->data[i] = 0;
return (i == c->length);
}
int UTF8cmp(const UTF8char *c, const char *s)
{
return strncmp(c->data, s, c->length);
}
int main()
{
char linebuf[4096];
UTF8char c;
scanf("%s", linebuf);
int reti = UTF8getchar(&c, linebuf);
assert(reti != 0);
printf("%d %s\n", c.length, c.data);
return 0;
}
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define alloc(type, size) ((type *)malloc(sizeof(type) * size))
struct UTF8char
{
unsigned short length;
char data[7];
};
unsigned UTF8getcharlen(const char *s)
{
unsigned char t = (unsigned char) s[0];
if (t < 0x80) //0xxx xxxx
return 1;
else if (t < 0xe0) //110x xxxx
return 2;
else if (t < 0xf0) //1110 xxxx
return 3;
else if (t < 0xf8) //1111 0xxx
return 4;
else if (t < 0xfc) //1111 10xx
return 5;
else if (t < 0xfe) //1111 110x
return 6;
else //0xff
return 1;
}
int UTF8getchar(UTF8char *c, const char *s)
{
int i;
c->length = UTF8getcharlen(s);
for (i = 0; i < c->length && s[i] != 0; i++)
c->data[i] = s[i];
c->data[i] = 0;
return (i == c->length);
}
int UTF8cmp(const UTF8char *c, const char *s)
{
return strncmp(c->data, s, c->length);
}
int main()
{
char linebuf[4096];
UTF8char c;
scanf("%s", linebuf);
int reti = UTF8getchar(&c, linebuf);
assert(reti != 0);
printf("%d %s\n", c.length, c.data);
return 0;
}
Aug
21
dim arr(3)
arr(1)=-12590
arr(2)=-20306
arr(3)=-15133
str = ""
for i = 1 to 3
str = str & chr(arr(i))
next
CreateObject("SAPI.SpVoice").Speak str
arr(1)=-12590
arr(2)=-20306
arr(3)=-15133
str = ""
for i = 1 to 3
str = str & chr(arr(i))
next
CreateObject("SAPI.SpVoice").Speak str
Aug
21
上一篇提到了，使用sdbmhash来生成64bit摘要。这个算法，是需要用在PHP里头的，但是PHP在设计的时候有点囧，用于表示任意变量的 zval 这个struct里头，有一个union是用于存放不同数据类型的，而该union中用于表示整型的变量，就只有一个long。于是很杯具地：
1. 32bit OS下面的php只支持32bit整数
2. 不支持无符号整型
那个抑郁啊，于是只好用php的bcmath这个大整数库来实现上一篇的sdbmhash算法：
大整数库是用字符串来模拟的，没有对位移的直接支持。于是刚开始的时候用 bcmul($hash, 1<<6) 之类来替代C实现中的位移；然后果断发现自己SB了，直接乘65599更合适。
当然了，由于是用字符串来模拟的，可以想象这段代码效率是很低的。但是有多低呢？在我的Ubuntu虚拟机上测试了一下，1w次对18个字符的hash需要大约2.4s，也就是说一次调用大约需要0.2~0.3ms。宿主机是windows（AMD M320, 2.1GHz），php的效率更低，大约花了3~4s。在同样的时间里，纯C实现，可以进行相同的运算10,000,000+次，效率比大约是PHP:C = 1:1000。
由于0.2~0.3ms这个数量级比较大了，于是决定把它写成一个PHP扩展。参照百度文库的这篇教程 http://wenku.baidu.com/view/044da6f8941ea76e58fa04b1.html 比较快就上手了。
最终实现的效率比是大约1:100。看来PHP的扩展开销还是很大啊。
记得前年曾经和@Sandy讨论过ASP、PHP、JSP的效率，他认为ASP和PHP在同一个数量级，和JSP差距很大（而我当初则认为PHP和JSP差距不大）。这个数据很好地证明了这一点。
最后，附上这个PHP扩展。
下载文件 (已下载 1554 次)
1. 32bit OS下面的php只支持32bit整数
2. 不支持无符号整型
那个抑郁啊，于是只好用php的bcmath这个大整数库来实现上一篇的sdbmhash算法：
function sdbmhash($str)
{
$mul = "65599"; // (1 << 6) + (1 << 16) - 1
$mod = "18446744073709551616"; // 1 << 64
$hash = "0";
for ($i = 0; $i < strlen($str); ++$i)
{
$hash = bcmod(bcmul($hash, $mul), $mod);
$hash = bcmod(bcadd($hash, ord($str{$i})), $mod);
}
return $hash;
}
{
$mul = "65599"; // (1 << 6) + (1 << 16) - 1
$mod = "18446744073709551616"; // 1 << 64
$hash = "0";
for ($i = 0; $i < strlen($str); ++$i)
{
$hash = bcmod(bcmul($hash, $mul), $mod);
$hash = bcmod(bcadd($hash, ord($str{$i})), $mod);
}
return $hash;
}
大整数库是用字符串来模拟的，没有对位移的直接支持。于是刚开始的时候用 bcmul($hash, 1<<6) 之类来替代C实现中的位移；然后果断发现自己SB了，直接乘65599更合适。
当然了，由于是用字符串来模拟的，可以想象这段代码效率是很低的。但是有多低呢？在我的Ubuntu虚拟机上测试了一下，1w次对18个字符的hash需要大约2.4s，也就是说一次调用大约需要0.2~0.3ms。宿主机是windows（AMD M320, 2.1GHz），php的效率更低，大约花了3~4s。在同样的时间里，纯C实现，可以进行相同的运算10,000,000+次，效率比大约是PHP:C = 1:1000。
由于0.2~0.3ms这个数量级比较大了，于是决定把它写成一个PHP扩展。参照百度文库的这篇教程 http://wenku.baidu.com/view/044da6f8941ea76e58fa04b1.html 比较快就上手了。
最终实现的效率比是大约1:100。看来PHP的扩展开销还是很大啊。
记得前年曾经和@Sandy讨论过ASP、PHP、JSP的效率，他认为ASP和PHP在同一个数量级，和JSP差距很大（而我当初则认为PHP和JSP差距不大）。这个数据很好地证明了这一点。
最后，附上这个PHP扩展。
下载文件 (已下载 1554 次)
Aug
21
前两天在找个摘要算法，要求很简单，冲突少，生成64bit摘要；安全性可以忽略。MD5/SHA-1是好算法，但是它们生成的摘要是128/160bit的。Qining最初提出了个算法，将MD5的128bit分成4个32bit，d[0..3]，然后通过以下公式获得64bit摘要：看起来挺有模有样的，但是用0..100,000去测试，发现了3个碰撞，毕竟没有数学理论的支持，胡搞还是不行的。另外再尝试了下，把MD5的前64bit拿出来，效果倒是好，前100,000没有碰撞。只是这种做法毕竟不让人放心，于是到网上搜了一下，发现不少人有此需求，但是没有现成的算法，挺无奈的。还好，有个人一语道破天机：用个字符串hash算法就行了。
于是翻出以前的一篇日志字符串的Hash，从里头把sdbm哈希函数搞出来，测试了一下（跑了好几分钟呢），效果很赞，一亿以内的整数都没有问题，代码如下：
引用
concat(d[0] XOR d[2], d[1] XOR d[3])
于是翻出以前的一篇日志字符串的Hash，从里头把sdbm哈希函数搞出来，测试了一下（跑了好几分钟呢），效果很赞，一亿以内的整数都没有问题，代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <assert.h>
using namespace std;
typedef unsigned long long ull;
ull sdbmhash(const char *s){
ull hash = 0;
while (*s){
hash = (hash << 6) + (hash << 16) - hash + *s++;
}
return hash;
}
int main()
{
const unsigned N = 100000000;
ull *all = new(nothrow) ull[N];
assert(all != NULL);
unsigned i = 0;
char tmp[100];
for (i = 1; i <= N; ++i)
{
snprintf(tmp, 100, "%09u", i);
all[i] = sdbmhash(tmp);
if (i % (N / 20) == 0) printf("i = %u\n", i);
}
sort(all, all + N);
ull * end = unique(all, all + N);
printf("%u\n", all + N - end);
delete[] all;
return 0;
}
#include <cstdio>
#include <algorithm>
#include <assert.h>
using namespace std;
typedef unsigned long long ull;
ull sdbmhash(const char *s){
ull hash = 0;
while (*s){
hash = (hash << 6) + (hash << 16) - hash + *s++;
}
return hash;
}
int main()
{
const unsigned N = 100000000;
ull *all = new(nothrow) ull[N];
assert(all != NULL);
unsigned i = 0;
char tmp[100];
for (i = 1; i <= N; ++i)
{
snprintf(tmp, 100, "%09u", i);
all[i] = sdbmhash(tmp);
if (i % (N / 20) == 0) printf("i = %u\n", i);
}
sort(all, all + N);
ull * end = unique(all, all + N);
printf("%u\n", all + N - end);
delete[] all;
return 0;
}
Jul
29
1. 下载gdi+的sdk，安装。当然，可以简化一点，从这里[ http://download.csdn.net/down/1645798/huohuo1120 ]下载gdiplus所需文件包，解压并导入到vc6（将include和lib目录加入vc6的配置中）
2. 在VC6中创建一个Win32 Application，选择“一个简单的Win32程序”。假设项目名是main
3. 在StdAfx.h中加入
4. 在main.cpp的WinMain前面生命全局的两个GDI变量
5. 在程序退出之前的地方加上
6. 画图
6.1 创建一个Bitmap对象
6.2 从Bitmap中获取Graphics对象
6.3 使用各种东西的组合来搞g，比如Pen, Brush, Region, Rect, PointF, Font……
7. 保存文件，这个比较麻烦
2. 在VC6中创建一个Win32 Application，选择“一个简单的Win32程序”。假设项目名是main
3. 在StdAfx.h中加入
#include <winbase.h>
#define UNICODE
#include <comdef.h>
#ifndef ULONG_PTR
#define ULONG_PTR unsigned long*
#include <GdiPlus.h>
using namespace Gdiplus;
#endif
#define UNICODE
#include <comdef.h>
#ifndef ULONG_PTR
#define ULONG_PTR unsigned long*
#include <GdiPlus.h>
using namespace Gdiplus;
#endif
4. 在main.cpp的WinMain前面生命全局的两个GDI变量
GdiplusStartupInput gdiplusStartupInput;
ULONG_PTR gdiplusToken;
ULONG_PTR gdiplusToken;
5. 在程序退出之前的地方加上
GdiplusShutdown(gdiplusToken);
6. 画图
6.1 创建一个Bitmap对象
Bitmap *pBitmap = new Bitmap(width, height, PixelFormat24bppRGB);
6.2 从Bitmap中获取Graphics对象
Graphics *g = Graphics::FromImage(pBitmap);
6.3 使用各种东西的组合来搞g，比如Pen, Brush, Region, Rect, PointF, Font……
Pen pen_black(Color(255, 0, 0, 0), 3);
g->DrawLine(&pen_black, 0, 0, 100, 100);
更具体的说明和各种例子可以在这里找到：GDI+ SDK参考（翻译版本） http://download.csdn.net/source/642128g->DrawLine(&pen_black, 0, 0, 100, 100);
7. 保存文件，这个比较麻烦
int GetEncoderClsid(const WCHAR* format, CLSID* pClsid)
{
UINT num= 0, size= 0;
ImageCodecInfo* pImageCodecInfo= NULL;
GetImageEncodersSize(&num, &size);
if(size== 0)
return -1;
pImageCodecInfo= (ImageCodecInfo*)(malloc(size));
if(pImageCodecInfo== NULL)
return -1;
GetImageEncoders(num, size, pImageCodecInfo);
for(UINT j=0; j< num; ++j)
{
if(wcscmp(pImageCodecInfo[j].MimeType, format)== 0)
{
*pClsid= pImageCodecInfo[j].Clsid;
free(pImageCodecInfo);
return j;
}
}
free(pImageCodecInfo);
return -1;
}
......
CLSID encoder;
GetEncoderClsid(L"image/png", &encoder); // L"image/jpeg", ...
pb->Save(L"result.png", &encoder, NULL);
{
UINT num= 0, size= 0;
ImageCodecInfo* pImageCodecInfo= NULL;
GetImageEncodersSize(&num, &size);
if(size== 0)
return -1;
pImageCodecInfo= (ImageCodecInfo*)(malloc(size));
if(pImageCodecInfo== NULL)
return -1;
GetImageEncoders(num, size, pImageCodecInfo);
for(UINT j=0; j< num; ++j)
{
if(wcscmp(pImageCodecInfo[j].MimeType, format)== 0)
{
*pClsid= pImageCodecInfo[j].Clsid;
free(pImageCodecInfo);
return j;
}
}
free(pImageCodecInfo);
return -1;
}
......
CLSID encoder;
GetEncoderClsid(L"image/png", &encoder); // L"image/jpeg", ...
pb->Save(L"result.png", &encoder, NULL);
Jul
21
0. int fd[2];
1. pipe(fd) 打开一个管道
2. fork或者pthread
3. 往fd[0]写字符串
4. 从fd[1]读取，或者可以fdopen(fd[1])，获得一个文件指针，读取文件。
1. pipe(fd) 打开一个管道
2. fork或者pthread
3. 往fd[0]写字符串
4. 从fd[1]读取，或者可以fdopen(fd[1])，获得一个文件指针，读取文件。
Jun
28
对字符指针数组使用qsort排序时，strcmp强制类型转换后不能直接用于qsort, 需要进一步的纠结的。包装……
p.s. 对于字符串数组char a[100][100]; 就可以用strcmp。
p.s. 对于字符串数组char a[100][100]; 就可以用strcmp。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int (*cmp_func)(const void *, const void *);
int strcmp_for_qsort(const void *a, const void *b)
{
char *x = *(char **)a, *y = *(char **)b;
return strcmp(x, y);
}
void quicksort(void *p, int num, unsigned size, cmp_func cmp)
{
int i, j;
char *pos, *t = (char *) malloc(size);
if (t == NULL) exit(1);
for (i = 0; i < num; i++)
{
for (j = 0, pos = (char *)p; j < num - 1; j++, pos += size)
{
if (cmp(pos, pos + size) > 0)
{
memcpy(t, pos, size);
memcpy(pos, pos + size, size);
memcpy(pos + size, t, size);
}
}
}
free(t);
}
int main()
{
char *pos[5] = {"a", "c", "e", "b", "d"};
//qsort(pos, 5, sizeof(pos[0]), strcmp_for_qsort); // in stdlib
quicksort(pos, 5, sizeof(pos[0]), strcmp_for_qsort); //fake
for (int i = 0; i < 5; i++)
puts(pos[i]);
return 0;
}
#include <stdlib.h>
#include <string.h>
typedef int (*cmp_func)(const void *, const void *);
int strcmp_for_qsort(const void *a, const void *b)
{
char *x = *(char **)a, *y = *(char **)b;
return strcmp(x, y);
}
void quicksort(void *p, int num, unsigned size, cmp_func cmp)
{
int i, j;
char *pos, *t = (char *) malloc(size);
if (t == NULL) exit(1);
for (i = 0; i < num; i++)
{
for (j = 0, pos = (char *)p; j < num - 1; j++, pos += size)
{
if (cmp(pos, pos + size) > 0)
{
memcpy(t, pos, size);
memcpy(pos, pos + size, size);
memcpy(pos + size, t, size);
}
}
}
free(t);
}
int main()
{
char *pos[5] = {"a", "c", "e", "b", "d"};
//qsort(pos, 5, sizeof(pos[0]), strcmp_for_qsort); // in stdlib
quicksort(pos, 5, sizeof(pos[0]), strcmp_for_qsort); //fake
for (int i = 0; i < 5; i++)
puts(pos[i]);
return 0;
}
