老星头的JoJo技术花园

今天偶然在网上看到了猫抓老鼠问题，
当时也没多想，只觉得网上给出的程序的确有很多需要改进的地方，
就闷头闷脑的用 循环链表 和 递归 写了一个算法实现，后来发现
 这个问题实际上是经典的约瑟夫环问题的变种，那个晕啊。而且有
很多数学的方式来改进。。。。5555。。。
看来算法部分要恶补，嗯嗯。。。

问题：
一、问题描述
    现有n个老鼠围成一圆圈，有一只猫从任意位置开始吃老鼠，每次都隔一个老鼠吃，请给出最后一个老鼠的编号？题目要求是任给老鼠数n，输出猫最后吃的老鼠的编号。
二、我的解法
   N只老鼠成循环链表，从第一只开始，每次隔一个节点，删去一个节点，这样一直删下去，
   如果删去的节点的下一个节点已经是链表头了，则将链表头赋值为链表头的下下一个节点，
  递归调用删除函数；如果删去的节点的下下一个节点才是链表头，则将链表头赋值为链表头
  的下一个节 点， 递归调用删除函数；直至链表头的下下一个节点即是链表头，或链表头的下
  一个节点就是链表头，break,输出链表头的编号。（这样做的目的是每次调用删除函数都是从
  第一个节点删起。）

三 SOURCE:

   // CatMousePro.cpp : Defines the entry point for the console application.
//

#include "stdlib.h"
#include "stdio.h"
#include "string.h"

#define MOUSENUM 60

struct Mouse* headMouse;
struct Mouse* pervMouse;
struct Mouse* cat;// currentMouse Point
bool   eatType; // true means mouseNum is a 奇数，false is opposite
int    lastMouseNum;

struct Mouse{
 int  Num;
 struct Mouse* next;
};

void catEat(struct Mouse* headMouse)

{
  if(headMouse->next->next == headMouse || headMouse->next == headMouse)
  {
   lastMouseNum = headMouse->Num;
   return;
  } 
  

  cat = headMouse;
  //headMouse = cat->next;// because first mouse have been eated!
  while(1)//not eat one circle
  {
   pervMouse = cat->next;
   
   if(pervMouse->next == headMouse)
   {
    headMouse = headMouse->next;
    pervMouse->next = headMouse;
    break;
   }
   if(pervMouse->next->next == headMouse )
   {
    pervMouse->next = headMouse->next;
    headMouse = headMouse->next->next;
    break;
   }

   cat = cat->next->next;
   pervMouse->next = cat->next;
  }
  catEat(headMouse);
}

int main(int argc, char* argv[])
{
 Mouse mouse;
 mouse.Num=1;
 mouse.next = NULL;
 
 headMouse = &mouse;
 pervMouse = &mouse;
 
 //inital mouse circle
 for(int i=2;i<MOUSENUM+1;i++)
 {
  struct Mouse* newmouse = new struct Mouse;
  newmouse->Num =i;
  newmouse->next = NULL;

  pervMouse->next = newmouse;
  pervMouse = newmouse; 
 }
 pervMouse->next = headMouse;

 catEat(headMouse);
 //at begin ,eat first mouse

 printf("the last mouse num is:%d",lastMouseNum);

 return 0;
}

顺便给出该问题的数学解法：
设有N只老鼠，找到大于N的最小的2的X次方（记为M），
然后  2N-M 就是结果，这样编程应该很简单了吧？

 

上周为项目做了一个小工具，需要由一颗内存树生成XML文档。
由于是在WIN平台，C++环境下编程，所以我选择了APACHE项目下
的XERCES-C作为软件平台进行开发。

XERCES-C是一款优秀的XML开发包。对DOM,SAX等技术做了比较完美
的实现。相关的信息请查看
http:\\xml.apache.org\xerces-c

但是在开发中，遇到了一个不大不小的问题，就是将内存中的DOM树导出
到文件的时候，默认生成的XML文档的encoding属性是UTF-16编码的，
但是内容却是UTF-8编码的，这样的XML文档实际上是无法被程序处理的。
更郁闷的是，无论我如何设置DOMDocument ,DOMWriter的Encoding 属性，
输出的东西永远都是这个样子的。输入中文那更是想都别想了。

那么如何把XML文档的编码设置成GB2312呢？
我BAIDU，GOOGLE了半天，发现因为这个问题所困扰的兄弟还真不少，
而且也没有太有效的解决办法，甚至有一个哥们无奈之下，干脆自己写了
一个XML解析器（汗。。。）。

经过这几天的工作，我发现了一些这个问题的解决之道，愿与大家分享。

1。 对于文档对象DOMDocument ,在代码中一般是一个名为doc的指针，
它的方法setEncoding ,setAcutalEncoding 对于最后生成的XML代码的编码
好像是没有影响的，但是保险起见，先把他们都设置为
doc->setEncoding(XMLString::transcode("GB2312"));
doc->setAcutalEncoding(XMLString::transcode("GB2312"));
注意，最好是你在对DOM树操作前进行设置。

2。也是最重要的一点，我在网上看到大家一般是用
DOMWriter 的 writeToString 将内存中的DOM树写入文件的，
但是经过我试验，应该用 writeNode 方法将DOM树写入文件。
具体代码如下：

DOMWriter* writer = impl->createDOMWriter(); //其中的impl是文档对象实例
writer->setEncoding(XMLString::transcode("GB2312")); //注意，这和上面讲的doc不是同一个对象

XMLFormatTarget *mytarget;
mytarget = new LocalFileFormatTarget(".\example.xml"); // 这一行创建一个XMLTarget,指向你要写入的文件路径

writer->writeNode(mytarget,*doc);// doc是你的文档对象
writer->release();

用以上代码的方式生成的XML文档就是GB2312编码的了，
以后在文档中增删改查中文都没有问题了。

后记：
核心的问题实际上是不能用writeToString写入文件，改用
writeNode就可以了。由于writeToString实际上是返回了一个
char* ,然后我们又要用一些其他方式，比如fprintf等等方式，
将这个字符串写入文件，我怀疑是在这一步中，出了问题，
我们调用的写文件函数将其自动转码了。但是我将内存中
的这个char*直接输出到屏幕上的时候，居然也是UTF-16的，
估计真的是 writeToString 这个函数有问题吧。

基于XERCES-C编程的人本来就少，大部分人都是基于XERCES-J
在工作。所以XERCES-C相关的使用经验等东西网上就很少，
希望这篇文章可以帮助有需要的兄弟，同时也希望大家都把自己
的使用经验POST一下，共同进步：）

（PS:四个月更新一次blog,我彻底输给我自己了，T.T,以后再忙也要坚持更新）

 

话说当年,老美搞出了ASCII编码,用8个bit表示一个字符,
解决了计算机存储人类语言的问题.

要说当时那帮人真是有点小家子气,只顾解决英语,数字和一些简单符号
的存储问题,压根就没想过中文啊,拉丁文啊,藏文啊啥的怎么存储的问题.

随着计算机越来越普及,这个问题也就越来越尖锐了,总不能让全世界人民
都使用英语吧?于是,有这么两个组织,一个曰ISO,一个曰unicode组织,就开始
想办法了...

unicode想的办法比较简单,不是1个byte不够嘛?咱用两个byte存,大概够了吧?
这就是unicode 1.0 的实现.

要说人家ISO就是大气,也可能决策者们没过过几十K内存的苦日子,
大笔一挥,不就是1个byte不够吗?用4个byte够了吧?再用个几百年也够了吧?
这就是 ucs-4 的雏型.

随着一些稀奇古怪的文字需要并入unicode,unicode的决策者有点冒汗了,
咱有这么多稀奇古怪的字母呢? 要不再加点, 用 2byte + 4 bit 来存吧..
那4bit做为头,这下就又能表示很多奇怪的文字了....
这就是 unicode 2.0 的雏型

现在有了两套风格迥异的编码方式, 到底该用那个呢?
于是 unicode 组织 和 ISO 组织 达成了协议,就是你中有我,我中有你,
ucs-4 尽管有 32 bit 编码空间,只用 20 bit ,和 unicode 保持统一,unicode不作修改
这就是 ucs-4 和 unicode 2.0 了,狼狈为奸的结果 :)

后来在 2000 年 8 月 ,unicode 的工作人员为了显得自己不是吃白食的,
就小小修改了一下 unicode 2.0 的文档,做为unicode 3.0 发布了.没加一个新字符啊!!!!!!
(实际上, 有大约12种当前语言 和 数十种古代语言,如雅玛语,古希腊B类线形文字,
古波斯碶型文字还没有得到支持)

至此,编码方案算是统一了,接下来,咬牙切齿骂街的就变成程序员们了.
程序员的愤怒是有道理的,比如输入一篇100字的英文文章,如果用ASCII
编码,仅需要 100 byte ,而如果出现了哪怕一个古怪的字符而不得不用ucs-4 ,
就需要 400 byte ! 这对早期的程序员来说简直是灾难...就算对带宽有限得今天,
这也是个很重要得问题..

于是IETF推出了 UTF- 8 和 UTF-16 两种解决方案 (utf32用的太少,忽略)
 
utf 8 实际上是最聪明的编码方式,简单说,规则有三条
(1) ASCII 编码不变, 用 1 个byte 表示
(2) 一个 byte 不够 ,就用两个 byte
(3)两个还不够,就用三个byte,什么?还不够?
不可能,3个byte已经超过unicode 的表示极限了..你是外星人吗?

它带来了如下两大好处:
(1)平台无关性,windows下用UTF-8写的小说,别人在unix下照样能看..
(2)有标记位,一个字读不出来,不影响其他字.

utf 16 则是给笨一点的程序员准备的,简单说,规则有两条
(1) unicode 1.0 中的字符完全照搬 ,用2个byte
(2) unicode 2.0 继续照搬,   需要用 20 bit 表示的字符,用 2byte + 4bit 处理.

这下带来的可不是一点两点的坏处,
(1)由于是变长,且不按计算机字长(8bit)来变长,所以用utf16编码的
东东的解码就和CPU,操作系统的处理方式相关了,不利于交流
(2)一些本来具有特殊意义的字符无法被计算机正常处理
(3)以上两条就可以判它死刑了...其他害处不一一列举,

但是utf16最省空间倒是真的.毕竟是紧凑编码的,没有大段大段的000000000出现....

实际上,IETF比较希望UTF-8成为事实标准(RFC2279),
而UTF-16,也就是卖ISO和unicode个面子,实现一下而已(RFC2781)

而现实中,由于UTF-8的优异性能,得到了广泛的认可和使用.
比如现在大红大紫的XML,在XML1.0第二版规范中明确指出,
当用户没有指定XML文档的 encoding 属性的时候,自动使用
UTF-8编解码
(尽管我强烈建议大家注明 encoding 属性)

OK,大话结束!各位可以把西红柿,鸡蛋啥的扔上来了 :)

 

后记:
这几天在网上看到了几位朋友在问这几个概念,就
写了这个随笔解释一下目前编码技术的大概.实际上,
我认为在大多数情况下,编码对程序员都是透明的,
就算需要使用,各软件平台也各自实现了比较好的编解码
接口,所以不必太死扣技术细节.

各位高手看了权当一笑,需要了解的朋友做为入门知识看看,
我觉得还是有一定意义的 :)

如果有错误之处,请不吝指出,老星头的JOJO技术花园需要您的热情支持 :)!

 

 

 

 

 

首先faint一下,这个post页面我刷了N次才出来,寒一个先...

公元2005年11月6日,俺老星头的第一次blog开通了,哇哈哈哈哈哈,

说起申请blog的原因,还真是比较古董:我在别人的一个项目论坛
做xml相关的一些技术资料,也是用blog贴,但是由于是别人的项目
论坛,想说点什么都要前思后想的,这对自由惯了的我来说简直
太压抑了,于是,哼哼,干吗不自己申请一个blog呢?

当然也有个人原因,已经工作了一年半了,终于有些拿得出手得东东
可以和大家一起学习提高了嘛,而且进入工作得第二个年头以后,
发现自己无论技术,还是个人等等方面,都需要进行一下整理,提高了,
所以想借助blog这种形式,和大家一起学习提高,同时也是对自己得
一种督促.

在技术上,我发现自己到了一个相对迷茫得时期,unix,win平台,C/C++,
J2se,.net,Eclipse,asp,mysql等等尽管都学习并使用过,但是真正能说
精通的,也只有XML,SNMP两门技术,我深深知道术贵精不贵多的
道理,但是究竟什么才是正确的发展方向呢?C/C++的精深?还是
J2EE的涉猎?依托目前的TMN知识发展相关技能,还是继续钻研
如何成为好的programmer?我们程序员的出路到底在那里?技术专家?
项目经理?还是系统分析员?

唉,其实这些问题,IT专家也说不上个所以然..庸人自扰了,呵呵,
不管了,先吃成胖子再说,目前的计划是继续关注,钻研XML技术,
同时重新读一些经典的C/C++书,把底子再好好打牢实点,争取
明年考过系分...恩.....貌似不难完成吧.,..哈..哈哈(底气不足中)


遥想当年,以为CCNA了便一生衣食无忧,
遥想当年,以为高程了便锦衣玉食,
看看今天,依然要学习再学习,明白自己选择了一条不归路了.....

最近心情不错,工作挺忙的,在solaris下做开发,我的视野又一次
被拓宽,刚开始还不想参加那个项目,现在发现能拿着工资,又
能学习简直是天大的好事啊...而且好像凡是项目需要的东西,
我都学的能快点...这个.....看来自学的时候还是有够懒啊...


JOJO的技术花园,START A NEW LIFE!