My Idea of Project
1. My responsibility:
I will be an implantation team leader who has the duty not only to carry out the most important part of coding job of project, but also actively participate in the design stage to make sure the design is suitable for our capacity of coding team and the time limit of project. What’s more important is that a team leader should try all way to make every member of team to be actively involved in development. And co-ordinate the relations between members and relations between coding team and design, specification team. I should discover the capacity of each member of coding team and try to make good use of it. Besides that I need to use my experience to foresee all possible problem in each implementation phases. For example, at this starting stage I need to enlighten members to be not too ambitious to develop a complicated game with perfect ideal operations which is very common problem for less-experienced programmers who underestimate the difficulty simply because they never have the developing experience. On the other hand, I should always try not to discourage them too much because the motivation for developing an interesting game is sometimes more important than their coding ability and experiences.
I will need fully support from design and specification team who will clarify the idea and procedure of game and give out detailed blueprint of project. However, when I study carefully of their design, it will be surely for me to have various questions to feed back to them. And their modification or explanations will lead to more mature idea of development. I need to share these idea entirely with my coding team. During developing, the coding team will have various problems. Some of them may be technical ones which I am supposed to give technical support. Some of them may be related with specifications and designs. These questions need my validation and communication with design, specification team.
I also need to fully control the progress of development to ensure our project delivery in time. And check from time to time the quality of coding even we will surely have a member specialized in testing. Because the combination of codes from different programmer will involve complicated debugging technique which is by all means to be my duty.
2. The technique we will use::
1) Uniformed coding styles: In order to ease job of combination of source code from different programmer, it is preferably to set up standard coding style from very first beginning, such as naming of variables, constants, classes. Position of curly brackets etc.
2) Purely object-oriented programming: Try to make all closely related functions to become a class. Make sure all repeated code to become a function, because forgetting updating “copy-paste” code is one of biggest resource of bugs. In order to avoid different team coding similar functions, try to assign closely-related functionality job to sub-teams.
3) Another way to avoid repeating coding is to use inheritance in C++. i.e. Both letters and cards need to have a display method and the method is much similar. Then make letter class and card class both inherited from same base class, say token class which implements the display method. Therefore, whenever find out some common functionality in both card and letter class, place it into base class token.
4) In order to prevent global variable be accidentally modified, make sure all global variable become only available by method instead of direct access. It will also be easier for adding extra “validating” method when setting or “constraint” method when getting.
5) Version control: In order to avoid chaos in versions, each member should periodically backup. The total combination version of each team member should also be backed up whenever debugging finished. Since we are not using any version control tools like “cvs”, “source safe”, it will need the team leader to keep backing up combination version individually. I have setup a free news group in “Yahoo Group” which supplies free service of news group---for group communication, web storage----for uploading maximum 20M files for version control.
3. The development model we will use:
I will suggest that our team apply “incremental model” which builds one bigger build based on previous build. For example, we will try first build a “naked” game displaying program for purely displaying boards, rackets, score bars etc. After this, we will build a simple “scrabble” game which will use the displaying module. Then add a “rummy” game into project. Then develop the score-calculating system and combine both “scrabble” and “rummy”. Finally if time permits, we may upgrade our text-mode display interface to a graphic interface. Therefore, at each stage we will clearly see the result. It not only ease the job of debugging, but also the team members will see our progresses and have more interest and confidence in further development.
4. Possible technique will be used in graphic interface:
1) We will probably use different language to develop graphic input-output interface, such as Delphi, VB, Java etc.
2) The graphic interface is involving as less programming control part as possible because we need to finish all our control code in c++. Therefore the front end is purely a dummy program for purely transfer users' input and display the calculated result from back-end.
3) All program written in C++ will be made a "DLL" (dynamic linking library) with all public methods to be exported in "dll".
4) The game control algorithm must reside within C++ DLL.
5) The following is a simple demo of how to call DLL from C++.
a) To make a dll in c++:
First choose "new" from Visual C++, choose the project of "win32 dynamic library". Compile by press "F7".
file name: dlltest.cpp
extern "C" __declspec(dllexport) int ADDNUM(int num1, int num2);
int ADDNUM(int num1, int num2)
{
return num1+num2;
}
b) To make a call in other program in c++:
setup a project and copy the compiled file from a) into directory of your setup work space (folder that contain your source file). Compile the following
program and run it.
#include <iostream> #include <windows.h> //extern "C" __declspec( dllexport ) int ADDNUM(int num1, int num2); using namespace std; typedef int (*MyProc)(int, int); MyProc fun; int main() { int num1=5, num2=10; HINSTANCE handle; handle = LoadLibrary("dlltest.dll"); if (handle!=NULL) { fun = (MyProc)GetProcAddress(handle, "ADDNUM"); if (fun!=NULL) { cout<<fun(num1, num2)<<endl; } } FreeLibrary(handle); return 0; }
God Speed Us...
From: "nickhuang99" <nickhuang99@hotmail.com> Date: Tue Mar 16, 2004 2:41 am Subject: To: All programmers Hi all, 1. I think we MUST finish our project this week or we may have no time for thorough testing. So, everyone must speed up now! 2. Charles: Can you finish your scoreboard by friday? 3. David: Can you set up all message showing mechnism at "working area"? If you like, you can use my simple "background" class to make the message-displaying area looks better. 4. Mr. Liu and Zhang Hong An: have you started testing of all visual components? How about the the DFA control diagram? 5. My plan is by end of this week, our game can run, at least for some functions of game-playing. have a nice day, nick
Working Schedule
From: "hotmail" <nickhuang99@hotmail.com> Date: Thu Mar 18, 2004 4:08 am Subject: To:About working schedule Hi all,
The following is my plan for working schedule in this week:
1. Charles: I suggest you write the frame to be a "CFrame" class because David can also use it for message showing. As for the layout job, I think Mr. ZhangHongAn can do it, so, you just concentrate on your scoreboard and frame class.
2. Mr. Zhang Hong An: try to position all components to a better way and write down all those coordinates. Don't forget there is scoreboard from Charles and message from David.
3. David: Please organize all "prompting messages" and make all them to be an array with some meaning index. i.e. enum values( see the rovertype.h).
4. Mr. LiuXiangqun: continue testing and don't forget the color questions, save all your tests and prepare to demo them at end of this week during meeting. We need to vote for colors.
5. Mr. HuQiHui: concentrate on the report, we all rely on you! And I am sure you will not be short of real bug reports. :)
6. Angel and all design team, and all programmers: I suggest we meet at weekend:
a) evaluate the our program demo.
b) discuss what to improve and possibly decide some game rule changes.
c) Any suggestion of better game start and end graphic idea?
d) decide all color combination of all visual parts.
....
see you all tomorrow,
Nick Huang/Qingzhe Huang
Bug Report
From: "nickhuang99" <nickhuang99@hotmail.com> Date: Thu Mar 18, 2004 1:15 pm Subject: Re: bug report Hi all, Usually in software company they have a format to report bugs. So, let's do it this way: 1. I create a folder named "BugReport" in our "yahoogroup". So, whoever find a bug just post his report under that folder. Preferably each one create a subfolder to contain his report file. The folder name can be date or simply serial no., say bug001. bug002... 2. The format of bug report must contain following: a) The name who find it. b) Category of bug: such as logical, display error, calculation error, or serious bug like crashed. c) Description of bug: Under what circumstance the bug appears. Should include a senario description. Sometimes a picture is the best to do this job. So, usually you need to make a bug-picture. d) Bug picture: To make a bug picture, when the bug happens, press "print screen" key on your keyboard. (it ususally locates at upper-right of your keyboard with abbreviation like "prt sc" or something".) Open your windows "paint" from your "accessories". Click "paste" from menu then you got the screen snapshot on your "paint". You can even draw some marks on the picture by choosing tools in "paint". Save the picture as "jpeg" format instead of "bmp". And name it properly then upload to your bug report folder. 3. Mr. HuQiHui: I think maybe the third report does need some "bug report". If yes, why don't you design some "word template" and upload the template to group so that everyone can download? 4. Angel: can you do a demo of report by reporting the bug you find while forming word? have a nice day, nick
About Game Playing
From: "hotmail" <nickhuang99@hotmail.com>
Date: Thu Mar 18, 2004 11:17 am
Subject: Re: [comp-354] Re: about play game
to form a word, you need to select letters first and then press "form word", then you are asked to input x, y and direction . Key in x and y required to press enter, and direction means "v" or "h". Tell me how you do it to make program crash.
Nick Huang/Qingzhe Huang
From: "hotmail" <nickhuang99@hotmail.com>
Date: Thu Mar 18, 2004 3:56 am
Subject: Re: about play game
hi,
1. The idea of game playing is that you have to choose an action once a
time, or menu. For example, if you want to choose index of letter rack of
3, 5, 6, you have to press menu3(select letter) 3 times and after each time
you press 3, you enter the index:
The sequence of entered: 3(this for menu) 3 (for index 3) 3 (menu)
5(index) 3(menu) 6(index).
2. It is a good question! Do we allow player to form words more than once
during one round? (Angel, what do you think?) And the placed words on board
can be removed by choosing menu "cancel".
3. see no. 1
4. I will try to see if it is possible to use function key. but first I
need to rush to finish algorith.
have nice day,
Nick Huang/Qingzhe Huang
Concordia University
Department of Computer Science
COMP 354 --- Software Engineering I
NAME : |
Qingzhe huang |
STUDENT ID : |
5037735 |
General instructions and information:
· You must use this template to submit this assignment.
· All your discussions must relate to software process aspects, e.g. the different phases of the project, the use of templates, project management, etc.
· This is not an open whining session on your team mates, the course, or the project. I want to know what you have learned from the experience of this project from the perspective of applying a software process.
· All your answers must explicitly refer to your experience in this project.
· This is an individual report. Plagiarism will not be tolerated.
· Clarity of answers will be graded.
· Provide a clearly different answer in each box.
· Answers specifically realted to document templates must be discussed in section III.
Grades distribution
Section |
Grading |
I. Positive aspects of applying a software process |
40% |
II. Negative aspects of the software process we used in the project |
30% |
III. Positive and negative aspects of using document templates |
30% |
Total |
100% |
Based on your experience in this project, give two definite advantages of using a software process. Explain your answer.
1. Planning more helps more. This is not a trivial programming assignment and it is quite a project. You see the final program includes 20 classes, roughly 3000 lines of code. So, I would say the implementation really benefits from detailed planning. At the requirement stage, we thoroughly discussed every aspect of game and had a rather vivid view of whole game. It surely provides a lot of help for following design phase because our whole team had been familiar with the game running and had a common view of the game. During design phase, I strongly urged all programmers to join the discussion of design even it was the job of design group. It not only gave a more specific idea how it should work, but also I have to think for each functionality how it should be done. This proved to be really helpful. As leader of implementation, I could add my opinion into design so that some unimportant or too-difficult functionalities had been adjusted. What’s more, their analysis gave me a more specific view of each part of game. It finally helped me to design all visual components in an hierarchical way, combined with object-oriented style. I realized that since we were going to program in a “console” we can put all display-related details into the smallest unit----tile, which is actually one character. Then all other components would use this atomic unit as building blocks. It also eased frustration of other programmers as they are not familiar with windows API’s. During building program, we used many inheritance and composition idea to try not to write too much code within one single class so that not only cooperation between programmers but also maintenance in future would become easier. By careful design, I had a clear view of all parts of game. It help me to decide the functionalities to be implemented within each class. This effort reduced coupling between classes and made our programming team possible to do on a contract basis, or interface-basis. All in one word, without preparation of requirement and design phase, implementation would be able to go such smoothly.
|
2. Design not only guide implementation but also contribute to part of coding It maybe trivial to other people but I do think it is one of positive part of design. As I mentioned in above design did give me a clear and specific view of game and helped me to decide which functionality should be implemented in which class. Besides this the design group also physically helped implementation by writing down those basic function prototypes and named all interfaces of each class. This is actually a part of coding! For some programmers naming classes and functions is a fun, but for others it maybe a headache. Sometimes I am the second kind of people. More over the design group had provided all those game data’s. For example, each letter has a point value to be associated. This table of points is directly borrowed into my code. Another example is that all system messages is based on design and all these routine job was already done by design group. It more or less released me from those headaches of typing. So, in my point of view good design is integrally a part of implementation. |
|
Explain how you think this project should have been managed in a more efficient and effective manner by using a different software engineering approach, either by having a different overall process approach, or a different approach in a particular phase of the project. Give two different improvements. Note that your propositions must still fall under proper software engineering, e.g. « we should not have used a process at all » is not an acceptable answer.
1. The earlier we reach implementation, the better we can make it! In my point of view, all documents have only two solely purpose in software engineering process: a) to help better understanding and eventually to help implementation; b) to help possible future maintenance. But during our game project, there are just too many useless documents. Or at least I consider them to be low efficiency. We wasted a lot of time to produce some useless documents when we were still not clear about our project. During the implementation phase there are so many changes that nobody would ever bother to update those documents! Then the documents lost their purpose of existence! Why should we spend so much time on them if they are not quite useful or so easily to be modified? So, in my opinion, instead of spending so much time staying at stage of requirement and design, it is preferable for programmers to quickly jump to the stage of implementation and get some immediate feedback to design group. This situation is exactly described as drawback of waterfall model. However, even we understand this in lecture, we still make the same mistake in action. My experience in this project tells me that the earlier the implementation feedback we get, the less useless requirement and design job we would waste on. If I was given one chance to re-do this project, I would ask all my team to quickly program some basic frame work or prototype of game to let us have some idea of how many hours we may take to finish one single functionality. Then we would be naïve to waste our energy on designing impractical options which turns out to be greatly time-consuming and beyond our capability. 2. Success due to heroic efforts is a disaster to a team I was particular touched by this sentence when professor gave lecture on CMM. The programming power of our team is in great variance and this prevents me from implementing many requirements. And consequently I had to reduce many features of game in view of slow progress in coding. Playing hero is a pride of a person but a failure of a team. So, I am not sure if my claim to have done the 95% of coding alone is a showing off of personal programming ability or a proof of failed leadership. Software engineering resembles a lot in organization management. Resources should be used more properly. If I was given another chance to re-do this project, I may carefully choose my partner. It is not the reason that I don’t like to co-operate with them. On the contrary, they are all my best friends and we really enjoyed working with each other. The only problem is that many of them are lack of basic experience, even though it is the purpose of this course to expose to them. However, from pure software engineering perspective, a good composition of team is sometimes the only guarantee of success of a project. Appropriate allocation of various resources of software engineering is the best lesson I learned in this project. |
|
Based on your experience in this project, explain the advantages of using document templates. Explain your answer.
Document template is actually a guide of action. It is something like what is said in lecture of CMM level 3. All procedures in software engineering have been formulated by a series of documents. These document templates reflect the previous experience of others. It surely reduces our efforts to figure out what should be done and how should be done. The contents force us to think and understand the whole process of software engineering. |
Based on your experience in this project, explain the potential problems related to the use of document templates. Explain your answer.
The documents are too many! We spent more time in writing than coding! And many of documents are so easily becoming useless when implementation changes requirements. And documents without updating is in my opinion a garbage because it is quite often misleading! The purpose of document is two: a) to help understanding and eventually all to help implementation. Otherwise we are not programming but publishing documents! b) to help future maintenance. However, it seems that our documentation failed in both two aspects! First of all, I admit requirement and design phase did help us understand the problem. But nevertheless too much documents were written when we still had little idea about what we should do. The contents of many documents were either empty or impractical. In my opinion, if we use these documentation time more wisely, we should try to implement for a while and come back to write some documents. Then we may do better by acquire more specific idea of what we can do and cannot do. Second, as I said documents without updating is not only useless but quite often harmful because of misleading. There are so many changes in our implementation and soon we don’t bother to update those changes in documents especially programmers are coding in a short of time manner. Then what is purpose to give wrong information to those possible maintenance programmers?
|
I spent almost one whole day to re-check our dependency
because I believe our project cannot compete with other groups either in
splendid graphic interface or in data constraint functions. The only thing we
can make sure and we must make sure is the database design is in 3rd normal
form.
Among all dependency, the most tricky one is about the "schedule" which I try to
assert as following. Please check if I am wrong or I missed anything:
1. The schedule conceptually involved following 5 abstract objects:
employee, car, order, servicetype, date&time.
2. I observed that date and time is rather one object because we never use them
separately. Do you agree? And service type in short is "type".
3. The following is my assertion:
a) For any employee in a particular datetime, he can only do one type of
service, for a specific car, under a specific order.
That is :
employee+datetime -> car, order, type;
b) For any particular car at any particular datetime, it must be under a
specific order, if it is repaired by one or more employee.
That is:
car+ datetime -> order;
c) For any car which is under a specific order for a specific type of service,
it must be done by a specific employee at a specific datetime. That is:
car + type + order -> employee, datetime;
4. These are all dependencies I discovered for these particular objects. I
changed my program a little bit and the result is worth observing:
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
decomposition
#1:{employee_sin,car_plate_number,service_type,service_time,service_date}
dependency is:
employee_sin service_time service_date -> car_plate_number service_type ;
decomposition #2:{car_plate_number,service_time,service_date,order_id}
dependency is:
car_plate_number service_time service_date -> order_id ;
decomposition
#3:{employee_sin,car_plate_number,service_type,service_time,service_date,order_id}
dependency is:
employee_sin service_time service_date -> car_plate_number service_type ;
car_plate_number service_time service_date -> order_id ;
car_plate_number service_type order_id -> employee_sin service_time service_date
;
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
From above I observed that we made a serious mistakes: The primary key should be
only "car_plate_number service_type order_id". In our database, I include
employee_sin as part of primary key which will lead to a situation that "for a
particular order which has only one car with "oil change" service type, our
SUPERMAN employee brothers "Khalid" and "Jabobo" tried to repair it at two
different date time---June 11, 5:00PM and June11 3:00PM". This is because our
key include "employee". So, we allow two employee to repair same car with same
problem under same order as long as they repair it at different time or date.
The second point I observed is that our database is 3NF instead of BCNF. You
see, "car_plate_number service_time service_date -> order_id ;" is BCNF
violation but it fits 3NF because our candidate key is {employee_sin
service_time service_date} and {car_plate_number service_type order_id}. The LHS
of 2nd dependency "car_plate_number service_time service_date" is not a superkey,
but the RHS "order_id" is prime member of key.
To: Jean, I hope you can include above argument into our report which I think
the tutor will concentrate on Dependency and 3NF.
So, I will modify our table structure again and insert data automatically.
Speed up!
nick
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
The link for downloading the
dependency tool program, input file and result.
类C编译器是用PCYacc做的,DSP汇编译器是用BISON做的。因为生成的代码实现递归调用太难了,所以一直想手工实现。
当然,词法部分用DFA,语法分析用递归预测分析(表达式例外),从空间占用和运行时间考虑,这样可行吗?还有在表达式分析时用算符优先分析,可是对负号怎么处理比较好呢?还有"/",有时作选项用,有时作除号用,能实现吗?
我刚看过你的scanner,不知为什么不用状态表来实现呢?如果代码这样做,直接函数调用而无须函数指针数组也可以呀?当然,理解上,就是在函数中实现状态转移了。
结合scanner和parser是很好的,如果时间不够而且愿意,我想可以我可以试下,可以吗?
我认为,LL(1)算法还是比较好的,利于语义处理,时空比也因该比LR(1)强一些吧。当然,在文法定义上,后者稍占优势。
请版主指点。
> 黄兄你好!非常高兴你将我引为知己同好,诚如你所说,我对编译甚至于计算语言学都非常感兴趣,希望自己能看到自然语言被计算机理解的那一天,说远了。
> 如果觉得有利,我同意将通信整理后贴在网页上,只是有些想法比较仓促,远远不够成熟,黄兄见笑了。
>
非常佩服你的认真,想自己工作也有四年了,可是由于很少写日记,加上前两年做的又是数据库系统,学校里接受的知识大多还给老师了,所以积累知识有限,如有些地方不妥,望黄史指正。针对你的疑问,我的看法是这样的:
> 一、关于有些术语可能由于中英译文问题,有些走样,以后我尽力将相关英语也写出来,这样也许会好些。你说的很对,“算符优先分析”就是operator
precedence
analysis的意思,而“递归预测分析”在我手中的编译书籍上称呼是“预测分析”,不过我觉得它既然是递归下降(recursive-descent)的改进——利用First
set 与 Follow set预先读取一个字符或Token结合当前规则进行分析,就私自加上了“递归”。
>
二、之所以在分析表达式时利用算符优先分析,是因为它相对而言容易实现而且直观。方法就是你说的那样,利用两两算符之间的优先等级进行分析。“减号”与“负号”会有不同的优先级,不过在“A--B-C="的情况下,可能会出现岐义吧。另外一个疑惑我已知道答案了,就是利用关键字可识别不同情况下的“/”。
> 三、因为用YACC或其它工具生成的代码全局变量和静态变量太多,而且由于考虑不同操作系统下的编译用了太多的宏,所以阅读起来麻烦,修改代码比较困难。当然,完全可以写自己的主驱动代码。
>
四、同意黄兄你的看法,用表驱动(table-driven)是为了提高编译速度,我提出来只是想和你讨论另一种方法而已,没其它意思。而且你的这种实现方法也是很好的,因为利用状态表会影响代码的阅读理解,如果不考虑这层因素那完全可以在一个函数里去实现了(平衡函数调用开销与阅读理解)。
>
五、至于先去处“left-recursive”还是先去除“common-left-factor”都会遇到问题,我想会不会是你的文法定义中出现了一个大的回路,这种情况在现在的程序语言的文法定义中还是很少见的,如果是这样现在已经有了解决此问题的算法,不过可能比较难找(我也只知道有这种算法,可是名称和出处就不知道了,报歉)。
>
六、YACC及其变种只是至顶向下分析(LL)的一种应用,LLgen及其它则是至底向上(LR)的应用,当然还有很多。我所以看好至顶向下分析,是因为文法中出现的问题可以手工消除,而且LR能解决文法中的左递归、和共公因子也是有牺牲时空比的代价的。
> 我所做的两种编译器是针对项目的。
> 看过ScannerPro,我想对于字符跳转是可以直接转移状态的,所以是否可以合并StartComment、EndComment?还有CheckChar在其它-Check函数里还没有充利用,不知是不是?另外,词法扫描的文法定义是怎样的,用于什么场合,我也很想知道。
> 因为最近电脑刚被借走,我只有利用(周一至周五)晚上的时间来做词法分析和语法分析的结合,所以时间可能比较慢。黄兄得有心理准备啊,呵呵!
>
>
>
> 时间过得好快。
> 其实,YACC作为自动化生成工具,确实有很多值得为人称道的地方。可惜对它本
身的代码我试过想去读懂却一直没有做到,也许是自己太懒——下的功夫还不够吧,
Sign!如果纯属使用它,那也太简单了,还没有WORD复杂呢,真的。
> 近来对FPL产生了兴趣,在学习HASKELL语言,对其中的Monads和闭包
(closure)很不明白,若黄兄清楚,还望指点迷津!
> 和黄兄通的交流,使我感到自己对编译理论欠缺很多,看来得下功夫恶补了。算
符优先分析在以前学C语言时接触过表达式分析,可是现在对这种算法竟没有多少印象
!
> 至于LL与LR,黄兄分析得很清楚了,但是我在用LR时,也经常遇到S/S
与S/R冲突,不知LL在解决左递归与公共因子后会不会出现类似的问题?
> 版本维护我用的是SourceSafe,CVS还玩不转。
比如我们都知道n个元素全排列的个数是n!=nx(n-1)x(n-2)x...2x1,那么这个数列乘积是不是告诉我们迪归的时候每个迪归方程的作的“工作”?假如我们用最简单的“size”来迪归,每次减一个,那么递归方程的参数就是size,这个大家都很好理解,关键是我要做的工作或者说当前这个level我要产生的排列数也应该是这个数目,所以,我就应该寻找一个size=k where k=n, n-1, n-2, ... 2,1这样的排列发生方法。非常naive地,我们知道我可以任意选择这k个元素中的一个,不妨就是第一个,让他与所有k个元素交换一下位置,这样会产生k个不同的结果,(记得他和她自己交换位置也算一次。)这样,我们就设计出了一个全排列的算法(如下)。由此推广,假如我们知道某种结果的个数是一系列的等差数列的乘积(或者是某种有规律的数列的乘积)也许我们可以用递归的方式设计出一种算法,当然我想算法是一种操作所固有的,所谓“造物本天成,妙手偶得之”,谈不上“设计”,但是,至少帮助我们发现她吧?God, enlighten me!
#include <stdio.h> #include <stdlib.h> const int ArraySize=4; char buffer[ArraySize+1]; int counter=0; void permutation(int start); void swap(int i, int j); void initialize(); int main() { initialize(); //printf("%s\n", buffer); permutation(0); return 0; } void initialize() { for (int i=0; i<ArraySize; i++) { buffer[i]='0'+i; } buffer[ArraySize]='\0'; } void swap(int i, int j) { char temp; temp=buffer[i]; buffer[i]=buffer[j]; buffer[j]=temp; } void permutation(int start) { if (start==ArraySize-1) { printf("%d:%s\n", ++counter, buffer); } for (int i=start; i<ArraySize; i++) { swap(start, i); permutation(start+1); swap(start, i); } } 1:0123 2:0132 3:0213 4:0231 5:0321 6:0312 7:1023 8:1032 9:1203 10:1230 11:1320 12:1302 13:2103 14:2130 15:2013 16:2031 17:2301 18:2310 19:3120 20:3102 21:3210 22:3201 23:3021 24:3012 Press any key to continue
吃饱了撑得了
线性代数的老师很有意思,他同时也在教数学分析,不过我是在另一个长着山羊胡子的老头子的section里面。他曾经说过这门课不是宗教课,不是讲感觉,不是说一种belief可以随随便便地传递给别人。凡事都须证明,我在中国的时候,至少在高中期间数学孩子认为是学得不错的,可是这个不错也是有前提的,就是中国的数学教育是一种机械模仿,我有的时候生起气来,会过激地认为这种模式甚至可以训练猴子成为数学老师,因为,不断的机械模仿与反馈和巴普罗夫的条件反射没有本质的区别,(当然人这种动物从条件反射的角度看和狗也没有区别。)比如,我以前看到lim(f(x)+g(x))=lim(f(x)) + lim(g(x))会情不自禁地干及上帝让小学学的“分配律”又回到了高等数学。这么去看待问题以便理解记忆本来无可厚非,只是太无中生有了。学习c++操作符重载之后才意识到数学符号作为数学思想的表达的工具大大方便了交流,同时也如c++被某些人滥用后的操作符重载,变得面目全非,我从前在解数学题的时候,其实只是在不断地套用一个个“已知的模板”,进行“有一定深度限制的深度搜索”,也就是“极尽变换计算之能事”看是否和目标一致,如果经过若干步变换还是不行的话,或者达到尽头的话,就另辟新路。(不过,就是现在我难道不是这样吗?或者大多数人不是这样的??)有时候,所谓套用的摸板实在是似是而非,也就是,类似于c++函数里参数类型错误,我现在在向那一定是因为,我们人类有了“摸板”的思想,知道有很多操作室与类型无关的,于是想当然地套用了未经验证的操作。像前面所说的函数和的极限等于函数极限的和,这根本就是函数的某个性质,和操作符号+无关,怎么能谈得上什么分配律呢?可是我却可以硬生生地把lim当作一个操作符号来看待,除非我们把操作符当作二元函数来担待,否则是无意义的。
向量空间的概念实在是伟大,他一下子把我头脑中的很多不相关的东西穿了起来,作为一个知识结构非常的深刻。可以说所有的数学,甚至自然现象都可以用向量空间的概念来理解。
我模模糊糊地想,每个子空间都有一个basis可以span出整个子空间,也就是subspace is closed in all linear combination of a certain set of vector which may be linearly independent. 我在学自动机原理的时候也总是在用到某种语言可以使用某些最基本的alphabet来得到的,难道说这些个alphabet就是这个语言的basis?
不过最近学了线性变换对这个问题有了一点点新的认识,那就是实数与这个函数在某一点的极限存在着一个线性变换,他们本来是在不同的向量空间,因为满足线性变换导致我们可以这样看待:A linear transformation F: U-->V exists between real number and the limit of some function at some point such that they satisfy two properties:
1) F(u+v)=F(u)+F(v)
2) F(kv)=kF(v)
where u,v in U.
So, that is it, as simple as that.
教授讲了一个简单的矩阵应用“高斯销元法”的小的技巧,本身是为了引出"topological sort"的算法找出graph中"strongly-connected-component"的一个应用,这个冗长的话题不提,只是其中一个老外同学让他交换“列”让我糊涂了好久,下课一位仁兄指出教授错了,我听他解释了半天还是似懂非懂,地铁做到家门口才恍然大悟,可是地铁已经走出了十几公里了,想起三国演义里面曹操和杨修同时猜“绝妙好辞”的谜语时候,杨修当场想出来了,曹操骑马走出五里路才想出来,曹操夸奖杨修说自己比杨修的才智差了五里路,我想我至少比那位仁兄差了十几公里以上了。
问题是这样的:
A B C D E (1)
F G (2)
H I (3)
J K (4)
L M (5)
这样一个SPARSE的MATRIX,除了字母以外,其他的ENTRY都是0。要进行“高斯销元法”的话,怎样才好呢?首先,你知道直接作的话会在“下半个三角形”填充一队的非零数。所以,聪明的办法是(1)和(5)交换,(如下)
L M (5)
F G (2)
H I (3)
J K (4)
A B C D E (1)
然后,用(5)总共5次逐次销掉第一列,(2)总共1次销掉(1)的第二列,(3)总共1次销掉(1)的第三列。。。
L M (5)
N O P Q (2)
R S T (3)
U V (4)
W (1)
这些新的字母代表产生的新的非零数。这本来很清晰的,可是又一位外国仁兄在第二步时候将第一列于第五列交换,这简直是无稽之谈,首先,线性代数里面这一系列的操作时ROW-SPACE-EQUIVALENT的操作,做列交换纯粹无意义。其次,就算交换了,还是无法销元,这就是我上课听得稀里糊涂的地方。一个非常NICE的小的技巧被弄得无法理解。如果不做这种变幻,按部就班的销元的话操作次数是4+3+2+1=10也就是(N-1)*N/2,而现在变成了4+4=8也就是(N-1)+(N-1),这其中的差别的确是巨大。