??xml version="1.0" encoding="utf-8" standalone="yes"?>
1.1 Names
A name should be informative, concise, memorable, and pronounceable if possible.
* Use descriptive names for globals, short names for locals.
Global variables need names long enough and descriptive enough to remind the reader of their meaning.
It's also helpful to include a brief comment with the declaration of each global.
The longer the program, the more important is the choice of good, descriptive, systematic names.
* Be consistent.
Give related things related names that show their relationship and high-light their difference.
* Use active names for functions.
* Be accurate.
1.2 Expressions and Statements
* Indent to show structure.
A consistent indentation style is the lowest-energy way to make a program's structure self-evident.
* Use the natural form of expressions.
Write expressions as you might speak them aloud.
* Parenthesize to resolve ambiguity.
* Break up complex expressions.
* Be clear.
the goal is to write clear code, not clever code.
* Be careful with side effects.
1.3 Consistency and Idioms
* Use a consistent indentation and brace style.
* Use idioms for consistency.
A central part of learning any language is developing a familiarity with its idioms.
* Use else-ifs for multi-way decisions.
1.4 Function Macros
* Avoid function macros.
* Parenthesize the macro body and arguments.
In C++, inline functions avoid the syntactic trouble while offering whatever performance advantage macros might provide.
They are appropriate for short functions that set or retrieve a single value.
1.5 Magic Numbers
Magic numbers are the constants, array sizes, character positions, conversion factors, and other literal numric values that appear in programs.
* Given names to magic numbers.
* Define numbers as constants, not macros.
The C preprocessor is a powerful but blunt tool, however, and macros are a dangerous way to program because they change the lexical structure of the program underfoot. Let the language proper do the work.
* Use character constants, not integers.
* Use the language to calculate the size of an object.
1.6 Comments
* Don't belabor the obvious.
* Comment functions and global data.
* Don't comment bad code, rewrite it.
* Don't contradict the code.
* Clarify,don't confuse.
1.7 Why bother?
The main concerns of programming style: descriptive names, clearity in expressions, straightforward control flow, readability of code and comments, and the importance of consistence use of conventions and idioms in achieving all of these.
Well-written code is easier to read and to understand, almost surely has fewer errors, and is likely to be smaller than code that has been carelessly tossed together and never polished.
The key observation is that good style should be a matter of habit.
Once they become automatic, your subconscious will take care of many of the details for you, and even the code you produce under pressure will be better.
E序设计实践 - W??/span>
1. 风格
1.1 名字
一个名字应该是非Ş式的、简l的、容易记忆的Q如果可能的话,最好是能够D的?/span>
* 全局变量使用h说明性的名字Q局部变量用短名字?/span>
全局变量的名字应该够长Q具有够的说明性。给每个全局变量声明附一个简短注释也非常有帮助?/span>
对于长的E序Q选择那些好的、具有说明性的、系l化的名字就更加重要?/span>
* 保持一致性?/span>
* 函数采用动作性名字?/span>
* 要准。名字与其实C持准的对应?/span>
1.2 表达式和语句
* 用羃行显C程序的l构?/span>
采用一U一致的~行风格Q是使程序呈现出l构清晰的最省力的方法?/span>
* 使用表达式的自然形式?/span>
表达式应该写得你能大声念出来?/span>
* 用加括号的方式排除二义性?/span>
* 分解复杂的表辑ּ?/span>
* 要清晰?/span>
目标应该是写出最清晰的代码,而不是最巧妙的代码?/span>
* 心副作用?/span>
?/span>++q一c运符h副作用,它们除了q回一个值外Q还隐含地改变变量的倹{?/span>
1.3 一致性和习惯用法
* 使用一致的~排和加括号风格?/span>
如果你工作在一个不是自己写的程序上Q请注意保留E序原有的风根{?/span>
* Z一致性,使用习惯用法?/span>
在学习一个语a的过E中Q一个中心问题就是逐渐熟悉它的习惯用法?/span>
-----------------------------------------------
常见习惯用法之一是@环的形式?/span>
例如Q?/span>
for(i = 0; i < n; i++)
array[i] = 1.0;
C++?/span>Java里常见的另一UŞ式是把@环变量的声明也包括在内:
for(int i = 0; i < n; i++)
array[i] = 1.0;
-----------------------------------------------
下面?/span>C语言扫描一个链表的标准循环Q?/span>
for(p = list; p != NULL; p = p->next)
...
-----------------------------------------------
无穷循环Q?/span>
for( ;; )
...
?/span>
while(1)
...
-----------------------------------------------
常见的另一个惯用法是把一个赋值放q@环条仉Q?/span>
while( (c = getchar()) != EOF)
putchar(c);
-----------------------------------------------
一个不好的例子Q?/span>
char *p, buf[256];
gets(buf);
p = malloc(strlen(buf));
strcpy(p, buf);
问题1.
l不要用函?/span>getsQ因Z没办法限制它p入那儿读入内容的数量。这常常会导致一个安全性问题?/span>
问题2.
q有另一个问题:strlen求出的值没有计入串l尾?/span>'\0'字符Q?/span>strcpy却将复制它?/span>
习惯写法是:
p = malloc(strlen(buf)+1);
strcpy(p, buf);
或在C++里:
p = new char[strlen(buf)+1];
strcpy(p , buf);
如果q里没有+1Q就要当心?/span>
strdup可以佉K免上q错误变得更单。可?/span>strdup不是ANSI C标准中的内容?/span>
问题3.
上面两个版本都没有检?/span>malloc的返回倹{?/span>
在实际程序中Q对?/span>malloc?/span>realloc?/span>strdup及Q何牵涉到存储分配的函敎ͼ它们的返回值都必须做检查?/span>
-----------------------------------------------
* ?/span>else-if表达多\选择?/span>
多\选择的习惯表C法形式如下Q?/span>
if (condition1)
statement1
else if (condition2)
statement2
...
else if (conditionn)
statementn
else
default-statement
1.4 函数?/span>
* 避免使用函数宏?/span>
函数宏最常见的一个严重问题是Q如果一个参数在定义中出现多ơ,它就可能被多ơ求倹{?/span>
如果调用时的实际参数带有副作用,l果可能生一个难以捉摸的错误?/span>
例子Q?/span>
?/span><ctype.h>中:
#define isupper(c) ((c) >= 'A' && (c) <= 'Z')
如果q样调用
while (isupper(c = getchar())),
两次输入的字W?/span>c被分别与'A'?/span>'Z'比较了?/span>
C语言标准允许?/span>isupper及类似函数定义ؓ宏,但要求保证它们的参数只求gơ?/span>
如果希望更安全些Q那么就一定不要嵌套地使用?/span>getcharq种带有副作用的函数?/span>
改写如下Q?/span>
while ((c = getchar()) != EOF && isupper(c))
有时多次求值带来的是执行效率问题,而不是真正的错误?/span>
* l宏的体和参数都加上括号?/span>
如果一个操作比较复杂,或者它很具一般性,值得包装hQ那么还是应该用函数?/span>
C++提供?/span>inline函数既避免了语法斚w的麻烦,而且又可得到宏能够提供的执行效率Q很适合来定义那些设|或者提取一个值的短信函数?/span>
1.5 秘的数 Q翻译的有点...Q?/span>
秘的数包括各种常数、数l的大小、字W位|、变换因子以及程序中出现的其他以文字形式写出的数倹{?/span>
* l神U的数v个名字?/span>
* 把数定义为常敎ͼ不要定义为宏?/span>
C语言预处理程序是一个强有力的工P但是它又有些鲁莽?/span>
使用宏进行编E是一U很危险的方式,因ؓ宏会在背地里改变E序的词法结构。我们应该让语法d正确的工作?/span>
Q译者注Q预处理命o不是C语言本n的组成部分,而是一l辅助成分。这里说"让语a..."Q也是说不要用预处理命令做。)
* 使用字符形式的常量,不要用整数?/span>
例子Q?/span>
if (c >= 65 && c <= 90)
...
q种写法完全依赖于特D的字符表示方式?/span>
q样写更好些Q?/span>
if (c >= 'A' && c <= 'Z')
...
但是Q如果在某个~码字符集里的字母编码不是连l的Q或Ҏ其他字母Q那么这U描q就是错的?/span>
最好是直接使用库函数?/span>
if(isupper(c))
...
-----------------------------------------------
E序里许多上下文中经常出现的0。如果我们把每个0的类型写得更明确更清楚,对读E序的h理解其作用是很有帮助的?/span>
例如Q用 (void*)0 ?/span> NULL 表示C里的I指针|?/span>'\0'而不?/span>0表示字符串结I字节?/span>
然而在C++里h们都已经接受了用0Q而不?/span>NULLQ表C空指针?/span>Java里则定义了关键字null?/span>
* 利用语言去计对象的大小?/span>
不要对Q何数据类型用显式写出来的大?/span>
例:
char buf[1024];
fgets(buf, sizeof(buf), stdin);
对于那些可以看清楚的数组Q不是指针)Q下面的宏定义能计算出数l的元素个数Q?/span>
#define NELEMS(array) (sizeof(array) / sizeof(array[0]))
1.6 注释
* 不要大谈明显的东ѝ?/span>
注释应该提供那些不能一下子从代码中看到的东西,或者把那些散布在许多代码里的信息收集到一赗?/span>
* l函数和全局数据加注释?/span>
* 不要注释差的代码Q重写它?/span>
* 不要与代码矛盾?/span>
当你改变代码Ӟ一定要注意保证其中的注释是准确的?/span>
* 澄清情况Q不要添乱?/span>
注释应该在困隄地方量帮助读者,而不是给他们讄障碍?/span>
注释很重要,但是也不必盲目注释?/span>
注释是一U工P它的作用是帮助读者理解程序中的某些部分,而这些部分的意义不容易通过代码本n直接看到?/span>
1.7 ZҎ费心
注重E序设计的风|h说明性的名字、清晰的表达式、直截了当的控制、可ȝ代码和注释,以及在追求这些内Ҏ一致地使用某些规则和惯用法的重要性?/span>
书写良好的代码更Ҏ阅读和理解,几乎可以保证其中的错误更?/span>
好风格应该成ZU习惯?/span>
一旦这U习惯变成自动的东西Q你的潜意识׃帮助你照料许多细节问题,甚至你在工作压力下写出的代码也会更好?/span>
iostream为内|类型类型对象提供了输入输出支持Q同时也支持文g的输入输出,cȝ设计者可以通过对iostream? 的扩展,来支持自定义cd的输入输出操作?
Z么说要扩展才能提供支持呢Q我们来一个示例?%CODE{"cpp"}% #include
<stdio.h> #include
class Test { public: Test(int a=0,int b=0) { Test::a=a; Test::b=b; } int a; int b; }; int main() { Test t(100,50); printf("%???",t);//不明的输出格式 scanf("%???",t);//不明的输入格式 cout<<t<<endl;//同样不够明确 cin>>t;//同样不够明确 system("pause"); } %ENDCODE% ׃自定义类的特D性,在上面的代码中,无论你用c风格的输入输出,或者是c++的输入输出都不是不明的一个表C,׃c语言没有q算W重载机 ӞDstdio库的不可扩充性,让我们无法让printf()和scanf()支持对自定义cd象的扩充识别Q而c++是可以通过q算W重载机制扩? iostream库的Qɾpȝ能能够识别自定义cdQ从而让输入输出明确的知道他们该q什么,格式是什么?
在上例中我们之所以用printf与coutq行Ҏ目的是ؓ了告诉大ӞC与C++处理输入输出的根本不同,我们从cq的? 入输出可以很明显看出是函数调用方式,而c++的则是对象模式,cout和cin是ostreamcdistreamcȝ对象?
IOSstream ? | |
---|---|
fstream | iomainip |
ios | iosfwd |
iostream | istream |
ostream | sstream |
streambuf | strstream |
我们所熟悉的输入输出操作分别是由istream(输入?和ostream(输出?q两个类提供的,Z允许双向的输入/ 输出Q由istream和ostreamzZiostreamcR?
cȝl承关系见下图:
iostream库定义了以下三个标准对象:
输出主要由重载的左移操作W(<<Q来完成Q输入主要由重蝲的右UL作符(>>)完成:
q些标准的流对象都有默认的所对应的设备,见下表:
C++对象?/u> | 讑֤名称 | C中标准设备名 | 默认含义 |
---|---|---|---|
cin | 键盘 | stdin | 标准输入 |
cout | 昄器屏q? | stdout | 标准输出 |
cerr | 昄器屏q? | stderr | 标准错误输出 |
那么原理上E++有是如何利用cinQcout对象与左Ud右移q算W重载来实现输入输出的呢Q?
下面我们以输Zؓ例,说明其实现原理:
一句输句:cout<<"www.cndev-lab.com"Q,事实上调用的是 ostream& operator<<(ostream &temp,char *ps);q个q算W重载函敎ͼ׃q回的是对象的引用Q引用可以作为左g用,所以当E序中有cMcout<<"www.cndev- lab.com"<<"中国软g开发实验室";q样的语句出现的时候,p够构成连l输出?
׃iostream库不光支持对象的输入输出Q同时也支持文g的输入输出Q所以在详细讲解左移与右U运符重蝲只前Q我? 有必要先Ҏ件的输入输出以及输入输出的控制符有所了解?
׃文g讑֤q不像显C器屏幕与键盘那h标准默认讑֤Q所以它在fstream.h头文件中是没有像cout那样预先定义的全局 对象Q所以我们必自己定义一个该cȝ对象Q我们要以文件作备向文g输出信息(也就是向文g写数?Q那么就应该使用ofstreamcR?
ofstreamcȝ默认构造函数原形ؓQ?%CODE{"cpp"}% ofstream::ofstream(const char *filename,int mode = ios::out,int openprot = filebuf::openprot); %ENDCODE%
其中mode和openprotq两个参数的可选项表见下表Q?
mode 属性表 | |
ios::app | 以追加的方式打开文g |
ios::ate | 文g打开后定位到文g,ios:app包含有此属? |
ios::binary | 以二q制方式打开文gQ缺省的方式是文本方式。两U方式的区别见前? |
ios::in | 文g以输入方式打开 |
ios::out | 文g以输出方式打开 |
ios::trunc | 如果文g存在Q把文g长度设ؓ0 |
openprot 属性表 | |
属? | 含义 |
0 | 普通文Ӟ打开讉K |
1 | 只读文g |
2 | 隐含文g |
4 | pȝ文g |
实例代码如下Q?%CODE{"cpp"}% #include
int main() { ofstream myfile("c:\\1.txt",ios::out|ios::trunc,0); myfile<<"中国软g开发实验室"<<endl<<"|址Q?<<"www.cndev- lab.com"; myfile.close() system("pause"); } %ENDCODE% 文g使用完后可以使用close成员函数关闭文g?
ios::app加模式,在用追加模式的时候同时进行文件状态的判断是一个比较好的习惯?
CZ如下Q?
%CODE{"cpp"}% #include
在定义ifstream和ofstreamcd象的时候,我们也可以不指定文g。以后可以通过成员函数open()昑ּ的把一 个文件连接到一个类对象上?
例如Q?
%CODE{"cpp"}% #include
代码如下Q?%CODE{"cpp"}% #include
我们在简单介l过ofstreamcdifstreamcdQ我们再来看一下fstreamc,fstreamcL? iostreamz而来Qfstreamcd象可以同Ҏ件进行读写操作?
CZ代码如下Q?%CODE{"cpp"}% #include
myfile.open("c:\\1.txt",ios::in,0); if(myfile) { cout<<"文g读错?文g可能丢失!"<<endl; system("pause"); exit(1); } char ch; while(myfile.get(ch)) { cout.put(ch); } myfile.close(); system("pause"); } %ENDCODE% ׃fstreamcd以对文g同时q行d操作Q所以对它的对象q行初始话的时候一定要昑ּ的指定mode和openprot参数?
接下来我们来学习一下串类的基知识Q什么叫串流c?
我们先看看看C++是如何对C风格的字W串进行控制的QC中的字符串其实也是字符数组Q字W数l内的数据在内存中的位置? 排列是连l的Q我们通常?char str[size]或者char *str的方式声明创建C风格字符数组Qؓ了能让字W数l作备ƈ提供输入输出操作QC++引入了ostrstream、istrstream? strstreamq三个类Q要使用他们创徏对象必d含strstream.h头文件?
istrstreamcL从istreamQ输入流c)和strstreambaseQ字W串基c)z? 来,ostrstream是从 ostreamQ输出流c)和strstreambaseQ字W串基c)z而来Qstrstream则是从iostream(输入输出类)和和 strstreambaseQ字W串基c)z而来?
他们的承关pd下图所C?
串流同样不是标准讑֤Q不会有预先定义好的全局对象Q所以不能直接操作,需要通过构造函数创建对象?
cistrstream的构造函数原形如下: %CODE{"cpp"}% istrstream::istrstream(const char *str,int size); %ENDCODE% 参数1表示字符串数l?而参?表示数组大小Q当size?Ӟ表示istrstreamcd象直接连接到由str所指向的内存空间ƈ以\0l尾? 字符丌Ӏ?
下面的示例代码就是利用istrstreamcd建类对象Q制定流输入讑֤为字W串数组Q通过它向一个字W型对象输入数据。代
码如下: %CODE{"cpp"}% #include
我们来一个示例代码: %CODE{"cpp"}% #include
int main() { stringstream ostr("ccc"); ostr.put('d'); ostr.put('e'); ostr<<"fg"; string gstr = ostr.str(); cout<<gstr<<endl;
char a; ostr>>a; cout<<a
system("pause"); } %ENDCODE%
除此而外Qstringstreamcȝ对象我们q常用它q行string与各U内|类型数据之间的转换。示例代码如下:
%CODE{"cpp"}% #include
int main() { stringstream sstr; //--------int转string----------- int a=100; string str; sstr<<a; sstr>>str; cout<<str<<endl; //--------string转char[]-------- sstr.clear();//如果你想通过使用同一stringstream对象实现多种cd的{换,h意在每一ơ{换之后都必须调用clear() 成员函数?string name = "colinguan"; char cname[200]; sstr<<name; sstr>>cname; cout<<cname; system("pause"); } %ENDCODE% 接下来我们来学习一下输?输出的状态标志的相关知识.
int main() { int a; cin>>a; cout<<cin.rdstate()<<endl; if(cin.rdstate() == ios::goodbit) { cout<<"输入数据的类型正,无错误!"<<endl; } if(cin.rdstate() == ios_base::failbit) { cout<<"输入数据cd错误Q非致命错误Q可清除输入~冲区挽回!"<<endl; } system("pause"); } %ENDCODE% 另一U方法则是用下面Q何一个函数来相应的输入/输出状态: %CODE{"cpp"}% bool bad(); bool eof(); bool fail(); bool good(); %ENDCODE%
下例CZQ表C出了上面各成员函数的用法: %CODE{"cpp"}% #include
int main() { int a; cin>>a; cout<<cin.rdstate()<<endl; if(cin.good()) { cout<<"输入数据的类型正,无错误!"<<endl; } if(cin.fail()) { cout<<"输入数据cd错误Q非致命错误Q可清除输入~冲区挽回!"<<endl; } system("pause"); } %ENDCODE% 如果错误发生Q那么流状态既被标Cؓ错误Q你必须清除q些错误状态,以你的E序能正适当地l运行。要清除错误状态,需使用clear()函数? 此函数带一个参敎ͼ它是你将要设为当前状态的标志倹{,只要ios::goodbit作ؓ实参?
CZ代码如下Q?%CODE{"cpp"}% #include
int main() { int a; cin>>a; cout<<cin.rdstate()<<endl; cin.clear(ios::goodbit); cout<<cin.rdstate()<<endl; system("pause"); } %ENDCODE% 通常当我们发现输入有错又需要改正的时候,使用clear()更改标记为正后Q同时也需要用get()成员函数清除输入~冲区,以达到重复输入的? 的?
CZ代码如下Q?%CODE{"cpp"}% #include
int main() { int a; while(1) { cin>>a;
if(cin)//条g可改写ؓcin.fail() { cout<<"输入有错!请重新输?<<endl;
cin.clear(); cin.get(); } else { cout<<a; break; } }
system("pause"); } %ENDCODE% 最后再l出一个对文g错误标记处理的例子Qm固学习,代码如下Q?
%CODE{"cpp"}% #include
int main() { ifstream myfile("c:\\1.txt",ios_base::in,0); if(myfile.fail()) { cout<<"文gdp|或指定文件不存在!"<<endl; } else { char ch; while(myfile.get(ch)) { cout<<ch; } if(myfile.eof()) { cout<<"文g内容已经全部d"<<endl; } while(myfile.get(ch)) { cout<<ch; } } system("pause"); } %ENDCODE%
对这些类的一个对象所做的W一个操作通常是它和一个真正的文g联系hQ也是说打开一个文件。被打开的文件在E序中由一个流对象 (stream object)来表C?(q些cȝ一个实? Q而对q个对象所做的M输入输出操作实际是对该文g所做的操作?/p>
要通过一个流对象打开一个文Ӟ我们使用它的成员函数open()Q?/p>
void open (const char * filename, openmode
mode);
q里filename 是一个字W串Q代表要打开的文件名Qmode 是以下标志符的一个组合:
ios::in | ??而打开 文g |
ios::out | ??而打开 文g |
ios::ate | 初始位置Q文件尾 |
ios::app | 所有输出附加在文g 末尾 |
ios::trunc | 如果文g已存在则? 删除该文?/td> |
ios::binary | 二进制方?/td> |
q些标识W可以被l合使用Q中间以”?#8221;操作W?|)间隔。例如,如果我们惌以二q制方式打开文g”example.bin” 来写入一些数据,我们可以通过以下方式调用成员函数openQ)来实玎ͼ
ofstream file;
ofstream,
ifstream ?fstream所有这些类的成员函数open 都包含了一个默认打开文g的方式,q三个类的默认方式各不相同:
file.open
("example.bin", ios::out | ios::app | ios::binary);
c?/th> | 参数的默认方?/th> |
---|---|
ofstream | ios::out | ios::trunc |
ifstream | ios::in |
fstream | ios::in | ios::out |
只有当函数被调用时没有声明方式参数的情况下,默认值才会被采用。如果函数被调用时声明了M参数Q默认值将被完全改写,而不会与调用参数l合?/p>
׃对类ofstream, ifstream ?fstream 的对象所q行的第一个操作通常都是打开文gQ这些类都有一个构造函数可以直接调用open 函数Qƈ拥有同样的参数。这P我们可以通过以下方式q行与上面同L定义对象和打开文g的操作:
ofstream file ("example.bin", ios::out |
ios::app | ios::binary);
两种打开文g的方式都是正的?/p>
你可以通过调用成员函数is_open()来检查一个文件是否已l被利的打开了:
bool is_open();
它返回一个布?bool)
|为真QtrueQ代表文件已l被利打开Q假( false )则相反?/p>
当文件读写操作完成之后,我们必须文件关闭以使文仉新变为可讉K的。关闭文仉要调用成员函数close()Q它负责缓存中的数据排攑և来ƈ 关闭文g。它的格式很单:
void close ();
q个函数一旦被调用Q原先的?
对象(stream object)可以被用来打开其它的文件了Q这个文件也可以重新被其它的进E?process)所有访问了?/p>
为防止流对象被销毁时q联pȝ打开的文Ӟ析构函数(destructor)会自动调用关闭函数close?/p>
cofstream, ifstream 和fstream 是分别从ostream, istream 和iostream 中引甌来的。这是Z?fstream 的对象可以用其父类的成员来讉K数据?/p>
一般来_我们用这些类与同控制?console)交互同样的成员函?cin ? cout)来进行输入输出。如下面的例题所C,我们使用重蝲的插入操作符<<Q?/p>
// writing on a text file #include <fiostream.h>int main () { ofstream examplefile (”example.txt”); if (examplefile.is_open()) { examplefile << “This is a line.\n”; examplefile << “This is another line.\n”; examplefile.close(); } return 0; } |
file example.txt This is a line. This is another line. |
从文件中d数据也可以用?cin的用同LҎQ?/p>
// reading a text file #include <iostream.h> #include <fstream.h> #include <stdlib.h>int main () { char buffer[256]; ifstream examplefile (”example.txt”); if (! examplefile.is_open()) { cout << “Error opening file”; exit (1); } while (! examplefile.eof() ) { examplefile.getline (buffer,100); cout << buffer << endl; } return 0; } |
This is a
line. This is another line. |
上面的例子读入一个文本文件的内容Q然后将它打印到屏幕上。注意我们用了一个新的成员函数叫做eof Q它是ifstream 从类 ios 中承过来的Q当到达文g末尾时返回true ?/p>
除了eof()以外Q还有一些验证流的状态的成员函数Q所有都q回bool型返回|Q?/p>
要想重置以上成员函数所查的状态标志,你可以用成员函数clear()Q没有参数?/p>
所有输?输出对?i/o streams objects)都有臛_一个流指针Q?/p>
我们可以通过使用以下成员函数来读出或配置q些指向中d位置的流指针Q?/p>
seekg ( pos_type position );
seekp ( pos_type
position );
使用q个原型Q流指针被改变ؓ指向从文件开始计的一个绝对位|。要求传入的参数cd与函?tellg 和tellp 的返回值类型相同?/p>
seekg ( off_type offset, seekdir direction );
seekp
( off_type offset, seekdir direction );
使用q个原型可以指定由参数direction军_的一个具体的指针开始计的一个位U?offset)。它可以是:
ios::beg | 从流开始位 |计的位移 |
ios::cur | 从流指针? 前位|开始计的位移 |
ios::end | 从流末尾? 开始计的位移 |
?指针 get ?put 的值对文本文g(text file)和二q制文g(binary file)的计方法都是不同的Q因为文本模式的文g中某些特D字W可能被修改。由于这个原因,对以文本文g模式打开的文件L使用seekg ? seekp的第一U原型,而且不要对tellg ?tellp 的返回D行修攏V对二进制文Ӟ你可以Q意用这些函敎ͼ应该不会有Q何意外的行ؓ产生?/p>
以下例子使用q些函数来获得一个二q制文g的大:
// obtaining file size #include <iostream.h> #include <fstream.h>const char * filename = “example.txt”;int main () { long l,m; ifstream file (filename, ios::in|ios::binary); l = file.tellg(); file.seekg (0, ios::end); m = file.tellg(); file.close(); cout << “size of ” << filename; cout << ” is ” << (m-l) << ” bytes.\n”; return 0; } |
size of
example.txt is 40 bytes. |
在二q制文g中,使用<< ?gt;>Q以及函敎ͼ如getlineQ来操作W输入和输出数据Q没有什么实际意义,虽然它们是符合语法的?/p>
?件流包括两个为顺序读写数据特D设计的成员函数Qwrite ?read。第一个函?(write) 是ostream 的一个成员函敎ͼ都是被ofstream所l承。而read 是istream 的一个成员函敎ͼ被ifstream 所l承。类 fstream 的对象同时拥有这两个函数。它们的原型是:
write ( char * buffer, streamsize size );
read (
char * buffer, streamsize size );
q里 buffer 是一块内存的地址Q用来存储或d数据。参数size 是一个整数|表示要从~存QbufferQ中d或写入的字符数?/p>
// reading binary file #include <iostream> #include <fstream.h>const char * filename = “example.txt”;int main () { char * buffer; long size; ifstream file (filename, ios::in|ios::binary|ios::ate); size = file.tellg(); file.seekg (0, ios::beg); buffer = new char [size]; file.read (buffer, size); file.close();cout << “the complete file is in a buffer”;delete[] buffer; return 0; } |
The
complete file is in a buffer |
?我们Ҏ件流q行操作的时候,它们与一个streambuf cd的缓?buffer)联系在一赗这个缓存(bufferQ实际是一块内存空_作ؓ?stream)和物理文件的媒介。例如,对于一个输出流Q? 每次成员函数put (写一个单个字W?被调用,q个字符不是直接被写入该输出所对应的物理文件中的,而是首先被插入到该流的缓存(bufferQ中?/p>
当缓存被排放出来(flush)Ӟ它里面的所有数据或者被写入物理媒质中(如果是一个输出流的话Q,或者简单的被抹?如果是一个输入流的话)? q个q程UCؓ同步(synchronization)Q它会在以下M情况下发生:
q就是我的数据了。现在,我要l这些数排序。假如我的电脑只能开?..99的数l,那计数排序算法最多对两位数进行排序。我把
每个八位C位两位地分成四段Q图1Q,分别q行四次计数排序。地球h都知道月份相同时应该看哪一日,因此我们看月份的大小时应该事先保证日已经有序。换
句话_我们先对“最不重?#8221;的部分进行排序。我们先Ҏ有数的最后两位进行一ơ计数排序(?Q。注意观??6LMM??6LMMQ本ơ排
序中它们的属性值相同,׃计数排序是稳定的Q因?月䆾那个排完后依然在1月䆾那个的前头。接下来我们对百位和千位q行排序Q图3Q。你可以看到两个
26日的MM在这一ơ排序中分出了大,而月份相同的MM依然保持日数有序Q因数排序是E_的)。最后我们对q䆾排序Q图4Q,完成整个法。大安
是跨世纪的好儿童Q因此没有图5了?br>
q?
U算法显然是正确的。它的复杂度一般写成O(d*(n+m))Q其中n表示n个数Qm是我开的数l大(本例中m=100Q,d是一个常数因子(本例?
d=4Q。我们认为它也是U性的?br>
问题五:q样的排序方法还有什么致命的~陷Q?/strong>
STOP! You should think for a while.
?
使数据有30位,我们也可以用d=5?的Radix法q行排序。但Q要是给定的数据有无I多位怎么办?有h_q可能么。这是可能的Q比如给定的数据
是小敎ͼ更准地_实数Q。基于比较的排序可以区分355/113?#960;?
个大Q但你不知道Radix排序需要精到哪一位。这下惨了,实数的出现把貌似高科技的线性时间排序打回了农业时代。这Ӟ桶排序再度出山,挽救了线性时
间排序悲惨的命运?br>
问题六:如何对实数进行线性时间排序?
STOP! You should think for a while.
?
们把问题化一下,l出的所有数都是0?之间的小数。如果不是,也可以把所有数同时除以一个大整数从而{化ؓq种形式。我们依然设立若q个Ӟ比如Q以
数点后面一位数Z据对所有数q行划分。我们仍然用链表把同一cȝC在一P不同的是Q每一个链表都是有序的。也是_每一ơ读C个新的数都要q?
行一ơ插入排序。看我们的例子:
A[]=
0.12345, 0.111, 0.618, 0.9, 0.99999
+---+---+---+---+---+---+---+---+---+---+
十分位: | 0 | 1 | 2 | 3 |
4 | 5 | 6 | 7 | 8 | 9 |
+---+-o-+---+---+---+---+-o-+---+---+-o-+
| | |
A[2]=0.111 A[3]=0.618 A[4]=0.9
| |
A[1]=0.12345 A[5]=0.99999
假如再下一个读入的数是
0.122222Q这个数需要插入到十分位ؓ1的那个链表里适当的位|。我们需要遍历该链表直到扑ֈW一个比0.122222大的敎ͼ在例子中则应该插?
到链表中A[2]和A[1]之间。最后,我们按顺序遍历所有链表,依次输出每个链表中的每个数?br> q个法昄是正的Q但复杂度显然不?
U性。事实上Q这U算法最坏情况下是O(n^2)的,因ؓ当所有数的十分位都相同时法是一个插入排序。和原来一P我们下面要计算法的q_旉复杂
度,我们希望q种法的^均复杂度是线性的?br> q次^均复杂度我们用最W的办法。我们将出所有可能出现的情况的L间复杂度Q除以ȝ
情况敎ͼ得到q_的复杂度是多?br> 每个数都可能属于10个桶中的一个,n个数ȝ情况?0^nU。这个值是我们庞大的算式的分母部分?
如果一个桶里有K个元素,那么只与q个桶有关的操作有O(K^2)ơ,它就是一ơ插入排序的操作ơ数。下面计,?0^nU情况中QK0=1有多种?
cK0=1表示Qn个数中只有一个数?hQ其余n-1个数的十分位只能在1?中选择。那么K0=1的情冉|C(n,1)*9^(n-1)Q而每
个K0=1的情况在0h中将产生1^2的复杂度。类似地QKi=p的情冉|为C(n,p)*9^(n-p)Q复杂度总计为C(n,p)*9^(n-
p)*p^2。枚举所有K的下标和p|累加hQ这个算式大家应该能写出来了Q但是这?#8230;…怎么啊。别怕,我们是搞计算机的Q拿出点和MO不一L?
西来。于是,Mathematica 5.0隆重dQ我做数学作业全靠它。它帮我们化简q个复杂的式子?br>
?
们遗憑֜发现Q虽然常数因子很(只有0.1Q,但算法的q_复杂度仍然是qx的。等一下,1/10的那?0是我们桶的个数吗Q那么我们ؓ什么不把桶?
个数弄大点?我们q脆用m来表C桶的个敎ͼ重新计算一ơ:
?
出来Q操作次CؓO(n+n^2/m)。发C么,如果m=Θ(n)的话Q^均复杂度变成了O(n)。也是_当桶的个数等于输入数据的个数Ӟ?
法是q_U性的?br> 我们在Hash表开散列的介l中重新提到q个l论?br>
且慢Q还有一个问题?0个桶以十分位?
数字归类Q那么n个桶用什么方法来分类呢?注意Q分cȝҎ需要满I一Q一个数分到每个桉的概率相同(q样才有我们上面的结论)Q二Q所有桶里容U_
素的范围必须是连l的。根据这两个条gQ我们有办法把所有数恰好分ؓncR我们的输入数据不是都在0?之间么?只需要看q些C以n的整数部分是多少?
行了Q读C个数后乘以n取整得几插入到几号桉。这本质上相当于把区间[0,1)q_分成n份?br>
问题七:?
没有复杂度低于线性的排序法
STOP! You should
think for a while.
我们从O(n^2)走向O(nlogn)Q又从O(nlogn)走向U性,
每一ơ我们都讨论了复杂度下限的问题,Ҏ讨论的结果提Z更优的算法。这ơȝ不行了,不可能有比线性还快的法了,因ؓ——你d、输出数据至就需
要线性的旉。排序算法之旅在U性时间复杂度q一站终止了Q所有十U排序算法到q里介绍完毕了?br>
文章有越写越?
的趋势了Q我查v来也来篏了。我又看了三遍,应该没问题了。群众的眼睛是雪亮的Q恳请大家帮我找错?br>
x
<- x # y
y <- x @ y
x <- x @ y
procedure
swap(var a,b:longint);
begin
a:=a + b;
b:=a - b;
a:=a - b;
end;
procedure swap(var a,b:longint);
begin
a:=a
xor b;
b:=a xor b;
a:=a xor b;
end;
var
a:word;
begin
a:=100;
a:=not a;
writeln(a);
end.
#include
<stdio.h>
int main()
{
unsigned short a=100;
a
= ~a;
printf( "%d\n", a );
return 0;
}
var
a,b:integer;
begin
a:=$0000;
b:=$0001;
write(a,' ',b,' ');
a:=$FFFE;
b:=$FFFF;
write(a,' ',b,' ');
a:=$7FFF;
b:=$8000;
writeln(a,'
',b);
end.
#include <stdio.h>
int main()
{
short
int a, b;
a = 0×0000;
b = 0×0001;
printf( "%d %d
", a, b );
a = 0xFFFE;
b = 0xFFFF;
printf( "%d %d
", a, b );
a = 0×7FFF;
b = 0×8000;
printf( "%d
%d\n", a, b );
return 0;
}
===== 真正强的东西来了Q?nbsp; =====
二进制中?有奇Cq是偶数?br> 我们可以用下面的代码来计?
一?2位整数的二进制中1的个数的奇偶性,当输入数据的二进制表C里有偶C数字1时程序输?Q有奇数个则输出1。例如,1314520的二q制
101000000111011011000中有9?Q则x=1314520时程序输??br>var
i,x,c:longint;
begin
readln(x);
c:=0;
for i:=1 to
32 do
begin
c:=c + x and 1;
x:=x shr 1;
end;
writeln( c and 1 );
end.
但这L效率q不高,位运的奇之处q?
没有体现出来?br> 同样是判断二q制?的个数的奇偶性,下面q段代码强了。你能看个代码的原理吗?var
x:longint;
begin
readln(x);
x:=x xor (x shr 1);
x:=x xor (x shr 2);
x:=x xor (x shr 4);
x:=x xor (x shr 8);
x:=x xor (x shr 16);
writeln(x and 1);
end.
Z说明
上面q段代码的原理,我们q是?314520出来说事?314520的二q制?01000000111011011000Q第一ơ异或操作的l果?
下:
00000000000101000000111011011000
XOR 0000000000010100000011101101100
---------------------------------------
00000000000111100000100110110100
?
到的l果是一个新的二q制敎ͼ其中双vWi位上的数表示原数中第i和i+1位上有奇C1q是偶数?。比如,最双那个0表示原数末两位有偶数?Q右
L3位上?pC原数的q个位置和前一个位|中有奇C1。对q个数进行第二次异或的结果如下:
00000000000111100000100110110100
XOR
000000000001111000001001101101
---------------------------------------
00000000000110011000101111011001
l?
果里的每?表示原数的该位置及其前面三个位置中共有奇C1Q每?pC原数对应的四个位置上共偶数?。一直做到第五次异或l束后,得到的二q制?
的最末位pC整?2位数里有多少?Q这是我们最l想要的{案?br>
计算二进制中?的个?br> 同样假设x是一?
32位整数。经q下面五ơ赋值后Qx的值就是原数的二进制表CZ数字1的个数。比如,初始时x?314520Q网友抓狂:能不能换一个数啊)Q那么最?
x变成了9Q它表示1314520的二q制中有9??br>x := (x and $55555555) + ((x shr 1)
and $55555555);
x := (x and $33333333) + ((x shr 2) and $33333333);
x := (x and $0F0F0F0F) + ((x shr 4) and $0F0F0F0F);
x := (x and
$00FF00FF) + ((x shr 8) and $00FF00FF);
x := (x and $0000FFFF) +
((x shr 16) and $0000FFFF);
Z便于解说Q我们下面仅说明q个E序是如何对一?位整数进
行处理的。我们拿数字211Q我们班某MM的生日)来开刀?11的二q制?1010011?br>
+---+---+---+---+---+---+---+---+
|
1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | <---原数
+---+---+---+---+---+---+---+---+
| 1
0 | 0 1 | 0 0 | 1 0 | <---W一ơ运后
+-------+-------+-------+-------+
| 0
0 1 1 | 0 0 1 0 | <---W二ơ运后
+---------------+---------------+
| 0
0 0 0 0 1 0 1 | <---W三ơ运后Q得Cؓ5
+-------------------------------+
?
个程序是一个分ȝ思想。第一ơ我们把每相ȝ两位加v来,得到每两位里1的个敎ͼ比如前两?0pC原数的前两位有2?。第二次我们l箋两两?
加,10+01=11Q?0+10=10Q得到的l果?0110010Q它表示原数?位有3?Q末4位有2?。最后一ơ我们把0011?010
加v来,得到的就是整个二q制?的个数。程序中巧妙C用取位和右移Q比如第二行?33333333的二q制?0110011001100….Q用
它和x做andq算q当于?为单位间隔取数。shr的作用就是让加法q算的相同数位对齐?br>
二分查找32位整数的前导0个数
q?
里用的C语言Q我直接Copy的Hacker's
Delight上的代码。这D代码写成C要好看些Q写成Pascal的话会出现很多begin和endQ搞得代码很隄。程序思想是二分查找,应该很简
单,我就不细说了?br>int nlz(unsigned x)
{
int n;
if (x
== 0) return(32);
n = 1;
if ((x >> 16) == 0) {n = n
+16; x = x <<16;}
if ((x >> 24) == 0) {n = n + 8; x = x
<< 8;}
if ((x >> 28) == 0) {n = n + 4; x = x <<
4;}
if ((x >> 30) == 0) {n = n + 2; x = x << 2;}
n = n - (x >> 31);
return n;
}
只用位运来?
l对?br> q是一个非常有的问题。大家先自己x吧,Ctrl+A昄{案?br> {案Q假设x?2位整敎ͼ则x xor
(not (x shr 31) + 1) + x shr 31的结果是x的绝对?br> x shr
31是二q制的最高位Q它用来表示x的符受如果它?Qx为正Q,则not (x shr 31) +
1{于$00000000Q异或Q何数l果都不变;如果最高位?QxQ,则not (x shr 31) +
1{于$FFFFFFFFQx异或它相当于所有数位取反,异或完后再加一?br>
高低位交?br> q个?/a>实际上是我出的,做ؓ学校内部NOIp模拟赛的W一题。题目是q样Q?br>
l出一个小?^32的正整数。这个数可以用一?2位的二进制数表示Q不?2位用0补Q。我们称q个二进 制数的前16位ؓ“高位”Q后16位ؓ“低位”。将它的高低位交换,我们可以得到一个新的数。试问这个新的数是多(用十q制表示Q?br> 例如Q? ?314520用二q制表示?000 0000 0001 0100 0000 1110 1101 1000Q添加了11个前?补?2位)Q其中前16位ؓ高位Q即0000 0000 0001 0100Q后16位ؓ低位Q即0000 1110 1101 1000。将它的高低位进行交换,我们得到了一个新的二q制?000 1110 1101 1000 0000 0000 0001 0100。它x十进制的249036820?
当时几乎没有人想到用一句位操作来代替冗长的E序。用位q算的话两句话就完了?br>var
n:dword;
begin
readln( n );
writeln( (n shr 16) or
(n shl 16) );
end.
而事实上QPascal有一个系l函数swap直接可以用?br>
?
q制逆序
下面的程序读入一?2位整数ƈ输出它的二进制倒序后所表示的数?br> 输入Q?
1314520 Q二q制?0000000000101000000111011011000Q?br> 输出Q?
460335104 Q二q制?0011011011100000010100000000000Q?br>var
x:dword;
begin
readln(x);
x := (x and $55555555) shl 1
or (x and $AAAAAAAA) shr 1;
x := (x and $33333333) shl 2 or (x
and $CCCCCCCC) shr 2;
x := (x and $0F0F0F0F) shl 4 or (x and
$F0F0F0F0) shr 4;
x := (x and $00FF00FF) shl 8 or (x and
$FF00FF00) shr 8;
x := (x and $0000FFFF) shl 16 or (x and
$FFFF0000) shr 16;
writeln(x);
end.
它的原理和刚才求二进制中1
的个数那个例题是大致相同的。程序首先交换每盔R两位上的敎ͼ以后把互怺换过的数看成一个整体,l箋q行?位ؓ单位、以4位ؓ单位的左叛_换操作。我
们再ơ用8位整?11来演C程序执行过E:
+---+---+---+---+---+---+---+---+
| 1 | 1 | 0
| 1 | 0 | 0 | 1 | 1 | <---原数
+---+---+---+---+---+---+---+---+
| 1
1 | 1 0 | 0 0 | 1 1 | <---W一ơ运后
+-------+-------+-------+-------+
| 1
0 1 1 | 1 1 0 0 | <---W二ơ运后
+---------------+---------------+
| 1
1 0 0 1 0 1 1 | <---W三ơ运后
+-------------------------------+
Copyright
也很?br>writeln('Matrix' , 42 XOR 105 , '原创Q{贴请注明出处');
今天我们来看两个E微复杂一点的例子?br>
n皇后问题位运版
n皇后问题是啥我就不说了吧Q学~程的肯定都见过。下?
的十多行代码是n皇后问题的一个高效位q算E序Q看到过的h都夸它牛。初始时Qupperlim:=(1 shl
n)-1。主E序调用test(0,0,0)后sum的值就是n皇后ȝ解数。拿q个MUSACOQ?.3sQ暴爽?br>procedure
test(row,ld,rd:longint);
var
pos,p:longint;
begin
{
1} if row<>upperlim then
{ 2} begin
{ 3}
pos:=upperlim and not (row or ld or rd);
{ 4} while pos<>0
do
{ 5} begin
{ 6} p:=pos and -pos;
{
7} pos:=pos-p;
{ 8} test(row+p,(ld+p)shl 1,(rd+p)shr
1);
{ 9} end;
{10} end
{11} else inc(sum);
end;
?
一看似乎完全摸不着头脑Q实际上整个E序是非常容易理解的。这里还是徏议大家自己单步运行一探究竟,实在没研I出来再看下面的解说?br>
?
普通算法一Pq是一个递归q程Q程序一行一行地L可以攄后的地方。过E带三个参数Qrow、ld和rdQ分别表C在U列和两个对角线方向的限制条?
下这一行的哪些地方不能放。我们以6×6的棋盘ؓ例,看看E序是怎么工作的。假讄在已l递归到第四层Q前三层攄子已l标在左图上了。红艌Ӏ蓝色和l色
的线分别表示三个方向上有冲突的位|,位于该行上的冲突位置qrow、ld和rd中的1来表C。把它们三个qv来,得到该行所有的位Q取反后得到所
有可以放的位|(用pos来表C)。前面说q?a相当于not a + 1Q这里的代码W?行就相当于pos and (not pos +
1)Q其l果是取出最双的那?。这PppC行的某个可以攑֭的位|,把它从pos中移除ƈ递归调用testq程。注意递归调用时三个参数的?
化,每个参数都加上了一个禁位,但两个对角线方向的禁位对下一行的影响需要^UM位。最后,如果递归到某个时候发现row=111111了,说明六个皇后
全放q去了,此时E序从第1行蟩到第11行,扑ֈ的解的个数加一?br>
~~~~====~~~~===== 华丽的分割线
=====~~~~====~~~~
Gray?br> 假如我有4个潜在的GFQ我需要决定最l到底和谁在一赗一个简单的办法
是Q依ơ和每个MM交往一D|_最后选择l我带来?#8220;满意?#8221;最大的MM。但看了dd牛的理论后,
事情开始变得复杂了Q我可以选择和多个MM在一赗这P需要考核的状态变成了2^4=16U(当然包括0000q一状态,因ؓ我有可能是玻璃)。现在的
问题是Q我应该用什么顺序来遍历q?6U状态呢Q?br> 传统的做法是Q用二进制数的顺序来遍历所有可能的l合。也是_我需要以
0000->0001->0010->0011->0100->…->1111q样的顺序对每种状态进行测试。这?
序很不U学Q很多时候状态的转移都很耗时。比如从0111?000时我需要暂时甩掉当前所有的3个MMQ然后去把第4个MM。同时改变所有MM与我?
关系是一件何{巨大的工程啊。因此,我希望知道,是否有一U方法可以得,从没有MMq一状态出发,每次只改变我和一个MM的关p(q或者甩Q,15ơ操
作后恰好遍历完所有可能的l合Q最l状态不一定是1111Q。大家自己先试一试看行不行?br> 解决q个问题的方法很巧妙。我们来说明Q假如我
们已l知道了n=2时的合法遍历序Q我们如何得到n=3的遍历顺序。显Ӟn=2的遍历顺序如下:
00
01
11
10
?
可能已经惛_了如何把上面的遍历顺序扩展到n=3的情cn=3时一共有8U状态,其中前面4个把n=2的遍历顺序照搬下来,然后把它们对U翻折下dƈ?
最前面加上1作ؓ后面4个状态:
000
001
011
010 ↑
--------
110 ↓
111
101
100
?
q种Ҏ得到的遍历顺序显然符合要求。首先,上面8个状态恰好是n=3时的所?U组合,因ؓ它们是在n=2的全部四U组合的基础上考虑选不选第3个元?
所得到的。然后我们看刎ͼ后面一半的状态应该和前面一半一h?#8220;盔R状态间仅一位不?#8221;的限Ӟ?#8220;镜面”处则是最前面那一位数不同。再ơ翻折三阉?
序Q我们就得到了刚才的问题的答案:
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
q?
U遍历顺序作ZU编码方式存在,叫做Gray码(写个中文让蜘蛛来抓:格雷码)。它的应用范围很qѝ比如,n阶的Gray码相当于在nl立方体上的
Hamilton回\Q因为沿着立方体上的边C步,nl坐标中只会有一个值改变。再比如QGray码和Hanoi塔问题等仗Gray码改变的是第几个
敎ͼHanoi塔就该移动哪个盘子。比如,3阶的Gray码每ơ改变的元素所在位|依ơؓ1-2-1-3-1-2-1Q这正好?阶Hanoi塔每ơ移?
盘子~号。如果我们可以快速求出Gray码的Wn个数是多,我们可以输ZQ意步数后Hanoi塔的Ud步骤。现在我告诉你,Gray码的Wn个数Q从
0vQ是n xor (n shr 1)Q你能想出来q是Z么吗Q先自己x吧?br>
下面我们把二q制数和Gray码都写在?
面,可以看到左边的数异或自n右移的结果就{于双的数?br>
二进制数 Gray?br> 000 000
001 001
010 011
011 010
100
110
101 111
110 101
111 100
?
二进制数的角度看Q?#8220;镜像”位置上的数即是对原数q行notq算后的l果。比如,W?个数010和倒数W?个数101的每一位都正好相反。假设这两个数分
别ؓx和yQ那么x xor (x shr 1)和y xor (y shr
1)的结果只有一点不同:后者的首位?Q前者的首位?。而这正好是Gray码的生成Ҏ。这p明了QGray码的Wn个数实是n xor (n
shr 1)?br>
今年四月?a target="_blank">mashuol?
我看?a target="_blank">q道?/a>Q是二维意义上的Gray码。题目大意是_??^(n+m)-1的数写成2^n *
2^m的矩阵,使得位置盔R两数的二q制表示只有一位之差。答案其实很单,所有数都是由m位的Gray码和n位Gray码拼接而成Q需要用左移操作?
orq算完成。完整的代码如下Q?br>var
x,y,m,n,u:longint;
begin
readln(m,n);
for x:=0 to 1 shl m-1 do begin
u:=(x xor (x
shr 1)) shl n; //输出数的左边是一个m位的Gray?br> for y:=0 to 1 shl n-1 do
write(u or (y xor (y shr 1)),' '); //q上一个n位Gray?br> writeln;
end;
end.
Matrix67原创
转脓h明出?/p>
位运简介及实用技巧(四)Q实战篇
下面
分n的是我自己写的三个代码,里面有些题目也是我自己出的。这些代码都是在我的Pascal时代写的Q恕不提供C语言了。代码写得ƈ不好Q我只是惛_诉大
家位q算在实战中的应用,包括了搜索和状态压~DP斚w的题目。其实大家可以在|上扑ֈ更多用位q算优化的题目,q里整理Z些自己写的代码,只是Z?
创系列文章的完整性。这一pd文章到这里就l束了,希望大家能有所收获?br> Matrix67原创Q{贴请注明出处?br>
Problem : 费解的开?br>
题目来源
06 qNOIp模拟赛(一Q?by Matrix67 W四?br>
问题描述
你玩q?#8220;拉灯”游戏吗?25盏灯排成一?×5的方 形。每一个灯都有一个开养I游戏者可以改变它的状态。每一步,游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生q锁反应Q和q个灯上下左右相 ȝ灯也要相应地改变其状态?br> 我们用数?#8220;1”表示一盏开着的灯Q用数字“0”表示关着的灯。下面这U状?br>
10111
01101
10111
10000
11011
? 改变了最左上角的灯的状态后变成:
01111
11101
10111
10000
11011
? 改变它正中间的灯后状态将变成Q?br>
01111
11001
11001
10100
11011
l? 定一些游戏的初始状态,~写E序判断游戏者是否可能在6步以内所有的灯都变亮?br>
输入格式
W一行有一个正整数nQ代表数 据中共有n个待解决的游戏初始状态?br> 以下若干行数据分为nl,每组数据?行,每行5个字W。每l数据描qC一个游戏的初始状态。各l数 据间用一个空行分隔?br> 对于30%的数据,n<=5Q?br> 对于100%的数据,n<=500?br>
? 出格?br> 输出数据一共有n行,每行有一个小于等?的整敎ͼ它表C对于输入数据中对应的游戏状态最需要几步才能所有灯变亮?br> ? 于某一个游戏初始状态,?步以内无法所有灯变亮Q请输出“-1”?br>
样例输入
3
00111
01011
10001
11010
11100
11101
11101
11110
11111
11111
01111
11111
11111
11111
11111
? 例输?br>3
2
-1
E序代码const
BigPrime=3214567;
MaxStep=6;
type
pointer=^rec;
rec=record
v:longint;
step:integer;
next:pointer;
end;
var
total:longint;
hash:array[0..BigPrime-1]of pointer;
q:array[1..400000]of rec;
function
update(a:longint;p:integer):longint;
begin
a:=a xor (1 shl p);
if p mod 5<>0 then a:=a xor (1 shl (p-1));
if (p+1) mod
5<>0 then a:=a xor (1 shl (p+1));
if p<20 then a:=a xor
(1 shl (p+5));
if p>4 then a:=a xor (1 shl (p-5));
exit(a);
end;
function find(a:longint;step:integer):boolean;
var
now:pointer;
begin
now:=hash[a mod BigPrime];
while
now<>nil do
begin
if now^.v=a then exit(true);
now:=now^.next;
end;
new(now);
now^.v:=a;
now^.step:=step;
now^.next:=hash[a mod BigPrime];
hash[a mod BigPrime]:=now;
total:=total+1;
exit(false);
end;
procedure solve;
var
p:integer;
close:longint=0;
open:longint=1;
begin
find(1 shl 25-1,0);
q[1].v:=1 shl 25-1;
q[1].step:=0;
repeat
inc(close);
for p:=0 to 24 do
if
not find(update(q[close].v,p),q[close].step+1) and
(q[close].step+1<MaxStep) then
begin
open:=open+1;
q[open].v:=update(q[close].v,p);
q[open].step:=q[close].step+1;
end;
until close>=open;
end;
procedure
print(a:longint);
var
now:pointer;
begin
now:=hash[a
mod BigPrime];
while now<>nil do
begin
if
now^.v=a then
begin
writeln(now^.step);
exit;
end;
now:=now^.next;
end;
writeln(-1);
end;
procedure main;
var
ch:char;
i,j,n:integer;
t:longint;
begin
readln(n);
for i:=1
to n do
begin
t:=0;
for j:=1 to 25 do
begin
read(ch);
t:=t*2+ord(ch)-48;
if j mod 5=0 then
readln;
end;
print(t);
if i<n then readln;
end;
end;
begin
solve;
main;
end.
======================= ?
感的分割U?nbsp; =======================
Problem : garden / 和MM逛花?br>
题目来源
07qMatrix67生日邀误 W? 四题
问题描述
花园设计Q简单就是美。Matrix67常去的花园有着非常单的布局Q花园的所有景点的位置都是“? ?#8221;了的Q这些景点可以看作是q面坐标上的格点。相ȝ景点之间有小路相q,q些\全部q于坐标u。景点和\l成了一?#8220;不完整的|格”?br> 一 个典型的花园布局如左图所C。花园布局??列的|格上,花园?6个景点的位置用红色标注在了图中。黑色线条表C景炚w的小路,其余灰色部分实际q不 存在?br>
Matrix67 的生日那天,他要带着他的MM在花园里游玩。Matrix67不会带MM两次l过同一个景点,因此每个景点最多被游览一ơ。他和他的MM边走边聊Q他们是 如此的投入以致于他们从不?#8220;d地拐?#8221;。也是_除非前方已没有景Ҏ是前方的景点已经讉Kq,否则他们会一直往前走下去。当前方景点不存在或已游 览过ӞMatrix67会带MM另选一个方向l前q。由于景点个数有限,讉Kq的景点越来越多,q早会出C能再走的情况Q即四个方向上的盔R景点 都访问过了)Q此时他们将l束花园的游览。Matrix67希望知道以这U方式游览花园是否有可能遍历所有的景点。Matrix67可以选择从Q意一个景 点开始游览,以Q意一个景点结束?br> 在上图所C的花园布局中,一U可能的游览方式如右图所C。这U浏览方式从(1,2)出发Q以(2,4) l束Q经q每个景Ҏ好一ơ?br>
输入格式
W一行输入两个用I格隔开的正整数m和nQ表C园被布局在m行n列的|格上?br> ? 下m行每行n个字W,字符“0”表示该位|没有景点,字符“1”表示对应位置有景炏V这些数字之间没有空根{?br>
输出格式
? 的程序需要寻找满?#8220;不主动拐?#8221;性质且遍历所有景点的游览路线?br> 如果没有q样的游览\U,误Z?#8220;Impossible”Q不带引 P注意大小写)?br> 如果存在游览路线Q请依次输出你的Ҏ中访问的景点的坐标,每行输出一个。坐标的表示格式?#8220;(x,y)”Q代表第x 行第y列?br> 如果有多U方案,你只需要输出其中一U即可。评系l可以判断你的方案的正确性?br>
样例输入
6 4
1100
1001
1111
1100
1110
1110
? 例输?br>(1,2)
(1,1)
(2,1)
(3,1)
(4,1)
(5,1)
(6,1)
(6,2)
(6,3)
(5,3)
(5,2)
(4,2)
(3,2)
(3,3)
(3,4)
(2,4)
? 据规?br> 对于30%的数据,n,m<=5Q?br> 对于100%的数据,n,m<=10?
E序代码Q?br>program garden;
const
dir:array[1..4,1..2]of integer=
((1,0),(0,1),(-1,0),(0,-1));
type
arr=array[1..10]of integer;
rec=record x,y:integer;end;
var
map:array[0..11,0..11]of boolean;
ans:array[1..100]of rec;
n,m,max:integer;
step:integer=1;
state:arr;
procedure
readp;
var
i,j:integer;
ch:char;
begin
readln(m,n);
for i:=1 to n do
begin
for j:=1 to m
do
begin
read(ch);
map[i,j]:=(ch='1');
inc(max,ord( map[i,j] ))
end;
readln;
end;
end;
procedure
writep;
var
i:integer;
begin
for i:=1 to step do
writeln(
'(' , ans[i].x , ',' , ans[i].y , ')' );
end;
procedure
solve(x,y:integer);
var
tx,ty,d:integer;
step_cache:integer;
state_cache:arr;
begin
step_cache:=step;
state_cache:=state;
if step=max then
begin
writep;
exit;
end;
for d:=1 to 4
do
begin
tx:=x+dir[d,1];
ty:=y+dir[d,2];
while
map[tx,ty] and ( not state[tx] and(1 shl (ty-1) )>0) do
begin
inc(step);
ans[step].x:=tx;
ans[step].y:=ty;
state[tx]:=state[tx] or ( 1 shl (ty-1) );
tx:=tx+dir[d,1];
ty:=ty+dir[d,2];
end;
tx:=tx-dir[d,1];
ty:=ty-dir[d,2];
if
(tx<>x) or (ty<>y) then solve(tx,ty);
state:=state_cache;
step:=step_cache;
end;
end;
{====main====}
var
i,j:integer;
begin
assign(input,'garden.in');
reset(input);
assign(output,'garden.out');
rewrite(output);
readp;
for i:=1 to n do
for j:=1 to m do
if map[i,j] then
begin
ans[1].x:=i;
ans[1].y:=j;
state[i]:=1
shl (j-1);
solve(i,j);
state[i]:=0;
end;
close(input);
close(output);
end.
======================= ?
感的分割U?nbsp; =======================
Problem : cowfood / 玉米?br>
题目来源
USACO月赛
? 题描q?br> 农夫U翰购买了一处肥沃的矩Ş牧场Q分成M*N(1<=M<=12; 1<=N<=12)个格子。他惛_那里的一些格子中U植味的玉c뀂遗憄是,有些格子区域的土地是贫瘠的,不能耕种?br> _明 的约知道奶牛们q食时不喜欢和别的牛盔RQ所以一旦在一个格子中U植玉米Q那么他׃会在盔R的格子中U植Q即没有两个被选中的格子拥有公p。他q没 有最l确定哪些格子要选择U植玉米?br> 作ؓ一个思想开明的人,农夫U翰希望考虑所有可行的选择格子U植Ҏ。由于太开明,他还考虑一个格? 都不选择的种植方案!请帮助农夫约确定种植方案L?br>
输入格式:
W一行:两个用空格分隔的整数M和N
W? 二行到第M+1行:Wi+1行描q牧场第i行每个格子的情况QN个用I格分隔的整敎ͼ表示q个格子是否可以U植Q?表示肥沃的、适合U植Q?表示贫瘠的? 不可U植Q?br>
输出格式
一个整敎ͼ农夫U翰可选择的方案L除以 100,000,000 的余?br>
样例输入
2 3
1 1 1
0 1 0
样例输出
9
样例说明
l可以种植玉c的格子~? P
1 2 3
4
? U一个格子的Ҏ有四U?1,2,3?)Q种植两个格子的Ҏ有三U?13,14?4)Q种植三个格子的Ҏ有一U?134)Q还有一U什么格子都? U?br> 4+3+1+1=9?br>
数据规模
对于30%的数据,N,M<=4Q?br> 对于 100%的数据,N,M<=12?
E序代码Q?br>program cowfood;
const
d=100000000;
MaxN=12;
var
f:array[0..MaxN,1..2000]of
longint;
w:array[1..2000,1..2000]of boolean;
st:array[0..2000]of integer;
map:array[0..MaxN]of integer;
m,n:integer;
function Impossible(a:integer):boolean;
var
i:integer;
flag:boolean=false;
begin
for i:=1 to MaxN do
begin
if flag and (a and 1=1) then exit(true);
flag:=(a
and 1=1);
a:=a shr 1;
end;
exit(false);
end;
function
Conflict(a,b:integer):boolean;
var
i:integer;
begin
for i:=1 to MaxN do
begin
if (a and 1=1) and (b and 1=1)
then exit(true);
a:=a shr 1;
b:=b shr 1;
end;
exit(false);
end;
function CanPlace(a,b:integer):boolean;
begin
exit(a or b=b);
end;
procedure FindSt;
var
i:integer;
begin
for i:=0 to 1 shl MaxN-1 do
if not
Impossible(i) then
begin
inc(st[0]);
st[st[0]]:=i;
end;
end;
procedure Init;
var
i,j:integer;
begin
for i:=1 to st[0] do
for j:=i to
st[0] do
if not Conflict(st[i],st[j]) then
begin
w[i,j]:=true;
w[j,i]:=true;
end;
end;
procedure
Readp;
var
i,j,t,v:integer;
begin
readln(m,n);
for i:=1 to m do
begin
v:=0;
for j:=1 to n do
begin
read(t);
v:=v*2+t;
end;
map[i]:=v;
readln;
end;
end;
procedure Solve;
var
i,j,k:integer;
begin
f[0,1]:=1;
map[0]:=1 shl n-1;
for i:=1 to m do
for
j:=1 to st[0] do
if not CanPlace(st[j],map[i]) then f[i,j]:=-1
else
for k:=1 to st[0] do if (f[i-1,k]<>-1) and w[j,k]
then
f[i,j]:=(f[i,j]+f[i-1,k]) mod d;
end;
procedure
Writep;
var
j:integer;
ans:longint=0;
begin
for
j:=1 to st[0] do
if f[m,j]<>-1 then ans:=(ans+f[m,j])
mod d;
writeln(ans);
end;
begin
assign(input,'cowfood.in');
reset(input);
assign(output,'cowfood.out');
rewrite(output);
FindSt;
Init;
Readp;
Solve;
Writep;
close(input);
close(output);
end.