Excel列编号(序号A、B、C…AA、AB…)英文字母字符生成算法备忘

近期很忙,博客也不怎么更新了,这里记录一个Excel扩展项目中的列编号生成算法实现。在VBA中,Excel的行可以是1、2、3、4、5…,但是Excel的列编号却是形如A、B、C…AA、AB…BA这样的编号模式,我期望将1、2、3、4、5转换为对应的Excel列编号,但对于我这种不太喜欢钻研算法的来说,确实有点棘手。

不过硬着头皮写了一段,并且也勉强能用,代码分享如下:

/**
*
*  buffer 字符缓冲区,用来存储A、B..AA..BB这样的转换结果
*  cch    字符缓冲区容量,最多可以容下字符数
*  num    表示要转换的数值数据
**/
char *TranslateToColumnName(char *buffer, int cch, int num)
{
    const int factor = 26;
    int f1 = (num) / (factor);
    int f2 = (num+1) - (f1) * factor;
    memset(buffer, 0, cch * sizeof(char));
 
    if (f1 == 0) {
        buffer[0] = 'A'+(f2-1);
        buffer[1] = '\0';
    } else {
        buffer[0] = 'A'+(f1-1);
        buffer[1] = 'A'+(f2-1);
    }
    return buffer;
}

有一天我在网上看到了现成的算法《如何将 Excel 列号转换为字母字符》,竟然还是微软官方提供的,看来我是重复造了一个轮子,微软的代码如下(VB实现):

继续阅读

Python计算并按比例获取随机票数

之前做的一个计票程序,需要用随机票数对程序进行样本测试,当然为了使测试接近于真实情况,对于三种投票结果(赞成、反对、弃权)按比例进行适当的调整。

下面我使用Python简单阐述一下这个简单的算法,首先获取一个随机票数,可以简单的通过随机一定范围的数字来实现,这个用Python实现比较简单,可以import random,然后通过random.randint(下限, 上限)来产生。我们可以先通过IDLE下面的脚本来查询使用方法:

import random
help(random.randint)
# -- output --
# Help on method randint in module random:
#
# randint(self, a, b) method of random.Random instance
#    Return random integer in range [a, b], 
#      including both end points.

继续阅读

简单即是美的,关于程序语言的想法

最近这段时间分别捣鼓了一下C#和PHP语言,然后还回顾了一下VBScript,颇有一些想法,所以记录下来,“简单即是美的(Simple is beauty)”这句话不愧是经典,想想我们现在庞大的互联网,还记得老师讲过互联网从设计之初就是从简原则,所以能够发展壮大到现在,而且还非常稳固。提到程序语言,大家可能会想到C语言,是的,C语言的设计也是以简洁为宗旨,从K&R的C语言的教材厚度也能看出这一点,简单意味着学习容易,上手快。现在的社会可以说是个快节奏的社会,大家都在想以最快的速度将知识变成生产力,所以基本没有人愿意在学习一门知识上耗费太多的时间,这也就是C语言如此流行的原因之一吧。

下面我想谈谈两种简单,1.语言结构简单(编程语法简单);2.功能简单(官方函数库少)。第1条除了C语言,估计Visual Basic以及其衍生品VBScript肯定是占优的,VB一度被认为是世界上最简单的编程语言之一。而且造就了大量的程序员,因为语言简单,只需要掌握那么点东西就可以写程序了。但是代码编写到最后,往往符合第1条的程序员容易抱怨到:“为什么没有这个功能”,然后就是拐弯抹角的去实现一个类似的功能,也许这个功能在别的什么程序语言中很容易实现。与第1条相反的估计就是像PHP或者JavaScript为代表了,话说PHP的内置函数,和一些特别的语法结构还真多,我一时还真不容易记住,所以写PHP代码经常要翻手册,还有就是JavaScript,这门语言我也在用,不过说实话,JavaScript的语法结构也很复杂,什么闭包、匿名函数概念的。复杂了也是有好处的,当然对于记忆力特别好的人而言,但是时间长了会形成一种定势,就是每写一段代码,脑海中总是想:“有没有内置的替代方法”、“语法结构应该能以另外一种方式写的更好”,当习惯一种复杂结构的编程语言后,再去研究一种简单的语言,恐怕就会抱怨语言结构简单,要这个没有,要那个功能不全等。第2条官方函数库少,VB及VBScript再次出线,是的,写了这么多年的VB或者VBScript程序,就那么一些内置函数,背都背下来了,所以写起程序基本上就不需要手册了,这点JavaScript也是类似的,相反的又是PHP,PHP有大量内置的官方函数,每次想一个功能,总有人说“嘿,有现成的内置函数”。久而久之我也不怎么想动脑筋了,遇到问题就是在翻手册,查找官方实现。这样的好处是省事,自己不要写某个功能了,而且官方的肯定稳定性不错,坏处是,觉得像PHP简直是大杂烩。

继续阅读

采样分类统计法计算分组票数

文章仅供参考

今天单位要求计票,近100个人,几千张选票,每张选票上有1~12人不等,选票内容有两大类,一类分为同意和不同意,一类分为优秀、称职、比较称职和不称职这几个选项,要求分别算出这些人两大类的选票数。

杯具的是,原始的选票,木有计算机啊,再NB的程序也派不上用场了,只有手工计票了,和同事讨论的几种计票方法,同事给出的意见是:先选择选票上第一个人,然后分别筛出得票最多的选项,比如说,这一堆选票,每张有张三、李四和王五三个人,首先选择张三,大概看了一下,发现张三得同意和优秀的票最多,我们把这些票筛选出来,然后统计不是这两个选项的票,这里只能采用笨方法,依次遍历两大类的各选项。这样发现计票确实容易了一些,因为大多数票已经被筛出了,然后数一下筛出的票数,再合计就得出了张三的所有选项的票数。

下午,同事有事外出,我单独找了一间大的会议室,然后准备计票,突然想到计算机上典型的以空间换时间的算法,也就是说时间快效率高,多数是以牺牲空间为代价的,典型的就是缓存,我们将经常会访问的数据存放在缓存里,这样可以避免多次查询数据库所带来的性能开销,访问的速度就会变快,而这个速度是要牺牲内存或者硬盘空间的;相反,如果空间小,更多地是要消耗性能,导致速度瓶颈的。

那么我又研究了一下刚才同事提出的思路,然后实际计了一组选票,得出以下结论:

1. 全部选择同意和优秀的比较多排第一,这类人多数对投票不感兴趣、不敢得罪人或者是不认识被选举人。

2. 全部选择同意和称职的人数排第二,这类人多数具备有第一条所述的特点,同时思想略有保守,对优秀比较感冒,或者本人要求比较严格,无论看什么都是有缺点的。

3. 全部选择不同意和称职的人数居第三,这类人多数原则上不想被选举人当选,既然不想被选举人当选,那么“优秀”就无从谈起,接下来就是“称职”、“比较称职”和“不称职”三种说法,既然选择不同意,可能觉得被选举人缺乏职务升迁的某种能力,但是对于其工作还是认可的,所以选择称职。

继续阅读

程序函数设计上的事务恢复与原子操作必要性

编译原理及编译器那个栏目一直空着,网站改版前是有一些文章的,改版后觉得价值不高就没有放上来,想先完成基础数据结构的函数库,可能学艺不深,一些简单的数据结构函数总是要改上很多次,本来是想从基础数据结构构建,直到一些复杂数据结构及算法的实现。事实上,问题开始逐渐凸显出来,作为一些简单的基础的数据结构,实现起来很容易,调用起来也很方便,没有什么问题,对于构筑于这些简单的数据结构上的复杂数据结构及算法貌似也实现了设想的功能,似乎这样没有问题,直到有一天我在做WEB数据库操作时想到:复杂数据及算法操作总是分成若干个操作简单数据结构的步骤,如果说这些若干步骤中,第N步出错,错误可以是内存读写失败或者权限等问题,那么对于第N步的致命错误,一般是直接返回,那么第N+1步是不会执行了,问题就在于第N-1步,如果第N-1步对原有数据造成了破坏,那么有没有类似于关系型数据库的事物恢复机制呢?如果说没有这种机制,那么在调用这个函数导致失败是小事,破坏了原有的数据就麻烦了。

可能最简单的做法就是在操作数据前对数据做一个拷贝,一旦失败并导致原有数据被破坏,则立即利用拷贝恢复被破坏的数据。数据量小的情况下这种方法确实简单方便,但是在应用复杂,数据量大的情况下,必然会导致存储空间和性能瓶颈,准备有时间好好研究一下数据库的原子操作的实现,一个可靠的数据算法函数库必须要有灾难恢复机制,否则就违背了函数设计的初衷了,即输入数据,得出正确结果,或者执行可以失败,但不能破坏了原有的数据。

基于左右值的无限级分类算法(1) – 插入节点

原创文章,未经允许,请勿转载!

关系型数据库一般都是以平面方式来存储我们的数据,这就造成了我们在实现一些数据结构上的麻烦,比如说如何实现高效的无限级的网站分类,这里MySQL的《Managing Hierarchical Data in MySQL》给出了一个比较好的办法,基于一种左右值的算法,这也是我目前接触到的查询比较高效的算法了,另外Gijs Van Tulder在sitepoint也写过一篇《Storing Hierarchical Data in a Database》文章专门讲解这个算法,我在这里再总结一下,首先看下面的这张图:

基于左右值无限级分类.png

通过这张图大家应该能很清晰的看出对于一种简单的树形结构分类的左右值处理的方式,这是一种类似于树的深度优先的遍历,其次这些左右权值很清晰的表明了一种隶属的包含关系,比如Fruit的左右值分别为1~6,那么说,所有在这个之间的值都是其子节点(Child Node)。对于数据库的遍历,我们可以很轻松的指定一个范围,然后执行一条SELECT查询语句。

继续阅读

Scripting.Dictionary字典对象按键名Key进行冒泡排序

最近加班比较多,代码写得有点乱,结果今天出现了个低级错误,原本想把Scripting.Dictionary对象的Item按照指定fnCompare函数作用的Key字段排序,原本以为很简单,于是就拿了个普通的冒泡排序就用了起来,结果问题就出现了,这里有问题的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
Option Explicit
 
Function fnCompare(key1, key2)
 If CInt(key1)>CInt(key2) Then
   fnCompare = 1
 ElseIf CInt(key1)<CInt(key2) Then
  fnCompare = -1
 Else
  fnCompare = 0
 End If
End Function
 
Function Sort(dict)
  Dim i,j, temp
  Dim keys,items
 
  For i = 0 To  dict.Count-1
    For j = i+1 To dict.Count - 1
	  keys = dict.Keys
	  items = dict.Items
      If fnCompare(keys(i), keys(j))>0 Then
        ' 交换Item项目
        temp = items(i)
        dict.Item(keys(i)) = items(j)
        dict.Item(keys(j)) = temp        
        ' 交换Key键名
        temp = keys(i)
        dict.Key(keys(i)) = keys(j)
        dict.Key(keys(j)) = temp
      End If
    Next
  Next
End Function
 
Sub VBMain()
  Dim dict
  Set dict = WSH.CreateObject("Scripting.Dictionary")
    dict.Add "2", "a"
    dict.Add "8", "b"
    dict.Add "1", "c"
    Sort dict
  Set dict = Nothing
End Sub
 
Call VBMain()

貌似这样看上去很正常,算法没有什么问题,交换Item后交换Key,貌似也没有问题,但是偏偏运行时出现了下面这个错误框。

继续阅读

C/C++函数传递参数需要指定缓冲区大小

原文发表于2009年2月5日 标题是《一个自己犯的C/C++错误》

以前自己写程序时经常犯的错误,后来才开始重视起来,为了更好的说明这个错误,我将演示代码贴出来:

#include <stdio.h> 
#include <string.h> 
#include <memory.h> 
 
// 写出缓冲区的16进制值
void print_byte(void *ptr, size_t size)
{
  unsigned i;
  unsigned char *bptr = (unsigned char *)ptr;
 
  for(i = 0; i < size; i++) {
    printf("%x ", *(bptr + i));
  }
  putchar('\n');
}
 
// 测试函数1 
void func_test(char *pbuf, size_t size)
{
  printf("SIZE=%d ? \n", sizeof(pbuf));
  memset(pbuf, 0, sizeof(pbuf));  // 我以前经常犯的错误 
  print_byte(pbuf, size);
}
 
// 测试函数2 
void func_test1(char *pbuf, size_t size)
{
  memset(pbuf, 0, size);
  print_byte(pbuf, size);
}
 
int main(void)
{
  char buffer[] = "0123456789";  // 字符缓冲区 
 
  printf("SIZE=%d\n", sizeof(buffer));
  print_byte(buffer, sizeof(buffer));
  memset(buffer, 0, sizeof(buffer));
  print_byte(buffer, sizeof(buffer));
 
  strcpy(buffer, "0123456789");
  func_test(buffer, sizeof(buffer));
  func_test1(buffer, sizeof(buffer));
 
  return 0;
}

可以看出,表面上这个错误是关于在函数内部将传参指向的缓冲区清零的,调试上述程序后发现主函数里定义的缓冲区被全部成功设置为0,而将这个缓冲区地址传入函数func_test后只有前4个字节被置0,那么问题出在哪里呢?问题就在sizeof上,在主函数上sizeof算得缓冲区为11(包含字符串结尾\0),而函数func_test里算得是4,很明显只是计算的指针的大小。

疑惑就在这里,buffer是数组名不就是地址吗,为什么传参后sizeof值就不算整个数组的大小而只算指针的大小呢?

其实这个问题很容易buffer是数组名,sizeof(数组名)算得的是整个数组占用的字节数,一旦赋值给任何指针(函数传参也相当于一种赋值),也就算的是这个指针的占用空间,和数组就没任何关系了。若还是算的事数组占用空间,那这个指针的占用就没办法计算了。

理解了这些就不难理解一些SDK提供的接口为什么要你传入缓冲区地址后还要你给出大小了,就像上面的修正函数func_test1。

通过这件事我知道什么事都不能想当然。不过对我过去的代码影响不是很大的因为在Windows API下经常使用固定大小MAX_PATH。于是大小就这样算了sizeof(TCHAR) * MAX_PATH。

编程中通过二进制状态位存储信息

原文发表于2009年3月7日

今天解皞同学询问了一道编程题,要求是用表驱动法也就是查表的办法解决,题目(部分)如下:

映射关系如下:
A, B, 和C 映射到 2
D, E, 和F 映射到 3
G, H, 和I 映射到 4
J, K, 和L 映射到 5
M, N, 和O 映射到 6
P, R, 和S 映射到 7
T, U, 和V 映射到 8
W, X, 和Y 映射到 9
Q和Z没有映射到任何数字。

可能最近一个链表的项目做晕头了,我的第一反应竟然是链表,后来想了下,这个应该使用普通数组的表结构会比较合理,我给出的建表方案如下:

映射关系是连续的,假设没有映射是1,那么映射关系应该是1-9这九个数字,化为数组下标应该是0-8。然后知道这是个一对多的关系,首先0对Q和Z、1对A、B和C……假设数组就是0~8的。

如何才能将一个数组下标对应的空间包含相应的多个联系呢?

我们可以通过状态位来判断,这里需要用到点位运算的知识。

设二元序列如下:
<0000 0001, A>
<0000 0010, B>
<0000 0100, C>
<0000 1000, D>
<0001 0000, E>
<0010 0000, F>
<0100 0000, G>
(省略若干)

大家应该能看出什么规律了,二进制的一位代表一个状态位,那么我们可以通过这些状态位索引字母A-Z。

那么一个无符号长整型(unsigned long)即可包含全部大写字母表的信息,比如包含A、B和C的信息,只要将A、B和C的二进制状态位按位或即可。

因此可以得到一张编码表:
<0x2010000> <Q, Z>
<0x0000007> <A, B, C>
<0x0000038> <D, E, F>
<0x00001c0> <G, H, I>
<0x0000e00> <J, K, L>
<0x0007000> <M, N, O>
<0x0068000> <P, R, S>
<0x0380000> <T, U, V>
<0x1c00000> <W, X, Y>

然后可以通过查这张表,然后用检测某位的方式判断映射关系,检测某位只需要按位与判断结果是否为0即可。

下面给出源代码:

#include <stdio.h> 
 
int main(void) {
 
  unsigned long letter_table[9] = 
    {0x2010000, 0x0000007, 0x0000038, 0x00001c0,
     0x0000e00, 0x0007000, 0x0068000, 0x0380000,  0x1c00000};
 
  int get_letter, i;
 
  puts("Enter letter [A-Z] ?");
  get_letter = getchar();
 
  if(get_letter < 0x41 || get_letter > 0x5a) {
    fprintf(stderr, "Error letter must A-Z");
    return 1;              
  }
 
  for(i = 0; i < 9; i++) {
    if((((unsigned long)(0x1 << (get_letter - 0x41))) &
      letter_table[i]) != 0) {
      if(i != 0)
        printf("found it!  @ %c = %d\n", get_letter, i + 1);
      else 
        printf("letter %c without number.\n", get_letter);
      break;              
    }      
  }
 
  return 0;    
}

以上源代码在Dev-CPP GCC下编译通过。

当然不见得这个就是效率很高的,我只是想通过这篇文章给大家编程时拓宽思路,比如位状态变化就是一个比较好的存储信息的方式。

如果想要查表效率很高,我觉得可以根据用户的具体输入,经过简单数学运算可以得到离结果最近的查表起始点,然后查找。

如果对于位操作比较感兴趣的可以参考我的前面的《简单介绍编程中位运算的使用》

简单介绍编程中位运算的使用

原文发表于2008年11月22日

在我刚刚接触C语言时,对于10进制转2进制这种数学运算很是反感,记得某次实验课上老师要求写一段10进制转换为2进制的C语言程序,我竟然忙活了半天没有搞定,本来以为很简单的,不就是除以二判断余数吗?但偏偏弄不好,后来接触到数据结构课知道每次余数判断需要将结果进栈,然后输出结果时出栈即可,代码后来自己搞定了。后来上过汇编课后了解了位运算。于是我写了如下代码,对,这就是进制转换,很简单。当然,如果你有更好的欢迎共同交流。

#include <stdio.h>   
int main(void)   
{ 
    int usr_input;   
    short i;   
    puts("Enter a number:");   
    scanf("%d", &usr_input);   
    for(i = ((sizeof(usr_input) << 3) - 1);
	i > -1; i--)   
    {   
        printf("%d", ((usr_input &
		     (0x1 << i)) == 0 ?
				0 : 1));   
        if((i & 3) == 0)   
            putchar(' ');    /* 这个if也可以省掉 */  
    }   
    putchar('\n');   
    return 0;   
}

位操作的魅力就在这里,代码简洁,当然最重要的一点还是位操作的效率比较高。缺点就是代码不易理解,不过我认为你对二进制位有深刻了解并且经常写一些位操作的代码的话这些代码你也会很容易理解的。

下面解释下这段进制转换的代码。

((sizeof(usr_input) << 3) – 1) 获取数据的位数,这里是int型,sizeof后为4,左移3位,左移1位即乘以2,这里即乘以8,结果是32,也就是说int型为32位(注:不同的机器可能sizeof的值是不同的,这里仅仅以Intel x86机型为例)。一般情况下二进制我们从右向左读,第1位也就是我们这里说的第0位,那么输出这个二进制,需要先输出最高的一位,也就是输出第31位。怎么判断这一位呢?这是我们下面要做的工作,学过汇编的知道,使用TEST指令即可判断位,而TEST指令做的是不写原值的按位与操作,所以要判断哪一位我们需要将那一位与1与,其余位与0与即可,比如这里的判断需要与的是1000 0000 0000 0000 0000 0000 0000 0000,如果结果是0,说明这一位是0,反之若不为0则这一位为1。但如何实现判断下一位和下下位的循环判断呢?其实我们可以设定一个初始值0000 0000 0000 0000 0000 0000 0000 0001即0x1,让其随循环次数进行左移即可。i & 3 其实这句是 i % 4,主要是为了美观,每四位输出空格。求余(模)一般对于求的是2的倍数的余数都可以用类似的按位与实现。

这段代码理解后可以看看下面的代码:

/* 转化为大写 */  
char *UCase(char *Source)   
{   
 long i=0;   
 do  
  if(*(Source+i) <= 'z' &&
	*(Source+i) >= 'a')   
   *(Source+i) &= 223; /* 将二进制第六位置为0 */  
 while(*(Source+i++));   
  return Source;   
}   
 
/* 转化为小写 */  
char *LCase(char *Source)   
{   
 long i=0;   
 do  
  if(*(Source+i) <= 'Z' &&
	*(Source+i) >= 'A')   
   *(Source+i) |= 32; /* 将二进制第六位置为1 */  
 while(*(Source+i++));   
  return Source;   
}

这段代码应该是比较好理解的,其实你只要用心观察过ASCII码表,分析其二进制后你就会发现一定的规律,然后也可以像上面的代码一样轻松的用位操作实现常用的功能。

如果我要让你写一段判断奇偶数的代码呢?很多人肯定认为,这还不简单,直接与2求余即可,学过汇编后,我才知道有比这个还方便的位操作方法,即直接判断最后一位是否为1,为1即为奇数,反之为偶数。怎么判断呢,上面说过了,用按位与即可,对0x1按位与。你会发现和刚才提到的求余的位操作简化有着相同之处,即模2。

再介绍个我较早接触的位操作,即交换两个整形变量。老师在授课时绝大多会和你讲,交换两个数需要临时变量什么的,然后要你写一个swap函数,其实在书上位操作那章介绍了一个不需要临时变量的整形交换方法。即异或。下次老师再要求你写交换两个整形的函数你就可以这样去写:

void swap(int *a, int *b)   
{   
    *a ^= *b;   
    *b ^= *a;   
    *a ^= *b;   
}

不相信吗?自己调试看看。这段代码类似与使用位运算的简单应用实现的密钥加密解密的功能。

下面提供一些,我写的用来操作位的宏:

#define BIT_TEST(src, pos) \
	((((src) & (0x1 << (pos))) == 0) ? 0 : 1)   
#define BIT_SET(src, pos) \
	((src) | (0x1 << (pos)))   
#define BIT_CLEAR(src, pos) \
	((src) & (~(0x1 << (pos))))   
#define BIT_TURN(src, pos) \
	((src) ^ (0x1 << (pos)))   
#define BIT_SIZE(type)     \
	(sizeof((type)) << 3)   
#define BIT_MOD(src0, src1) \
	((src0) & ((src1) - 1)) /* src1 must be 2*n */

解释:

BIT_TEST 输出src的pos位是0还是1。
BIT_SET 设置src的pos位为1。
BIT_CLEAR 设置src的pos位为0。
BIT_TURN 翻转src的pos位,即0变成1,1变成0。
BIT_SIZE 输出type型的位数。
BIT_MOD 求余(模),即将src0 % src1,特别提醒的是src1必须是2的倍数。

最后,我想说的是,这里提到的位操作均适用于整形数,最好不要尝试在浮点型上应用,以避免意想不到的后果。