searl1986 space

组合算法  
  本程序的思路是开一个数组，其下标表示1到m个数，数组元素的值为1表示其下标  
  代表的数被选中，为0则没选中。    
  首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。    
  然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为  
  “01”组合，同时将其左边的所有“1”全部移动到数组的最左端。    
  当第一个“1”移动到数组的m-n的位置，即n个“1”全部移动到最右端时，就得  
  到了最后一个组合。    
  例如求5中选3的组合：    
  1   1   1   0   0   //1,2,3    
  1   1   0   1   0   //1,2,4    
  1   0   1   1   0   //1,3,4    
  0   1   1   1   0   //2,3,4    
  1   1   0   0   1   //1,2,5    
  1   0   1   0   1   //1,3,5    
  0   1   1   0   1   //2,3,5    
  1   0   0   1   1   //1,4,5    
  0   1   0   1   1   //2,4,5    
  0   0   1   1   1   //3,4,5  

全排列算法  
  从1到N，输出全排列，共N！条。  
  分析：用N进制的方法吧。设一个N个单元的数组，对第一个单元做加一操作，满N进  
  一。每加一次一就判断一下各位数组单元有无重复，有则再转回去做加一操作，没  
  有则说明得到了一个排列方案。

/***********************************************/
void shift(char str[],int m)  /*定义循环左移函数*/
{
  int i,j;
  char temp=str[0];
  for (i=0;i<m;i++) str[i]=str[i+1];
  str[i]=temp;
}
void permutation(char str[],int m,int n) /*定义全排列函数*/
{
int k;
void shift(char str[],int m);
if (m<n)        /* 定义递归调用出口  */
  {
   for (k=0;k<=m;k++)
    {
     permutation(str,m+1,n); /*递归调用*/
     shift(str,m); /*调用左移函数*/
    }
  }
else printf("%s\t",str);
}
#include "stdio.h"
main()
{char str[]="ABCD"; /*全排列字符,可以任意多个(相应的下面排列函数中参数"4"改成全排列字符的个数)*/
clrscr();
permutation(str,0,4); /*这里参数0(下标)表示从第一个元素开始,4表示元素个数(不是下标)*/
getch();
}
/*********************************************/

下面我来解释一下,我花了近1天的时间,找到这样一个规律如下:
                           ┏ ABCD
                           ┣ BCDA
                 ┏ ABCD ━┫
                 ┃        ┣ CDAB
       ┏ ABCD ━╋ BCAD   ┗ DABC
       ┃        ┃         .
       ┃        ┗ CABD    .
ABCD ━┫                   .               
       ┃        ┏ BACD    .
       ┃        ┃         .
       ┗ BACD ━╋ ACBD   ┏ CBAD
                 ┃        ┣ BADC
                 ┗ CBAD ━┫
                           ┣ ADCB
                           ┗ DCBA
简化图如下所示 ==>
                     ┏ ABCD
                     ┣ BCDA
            ┏ ABC ━┫
            ┃       ┣ CDAB
    ┏ AB ━╋ BCA   ┗ DABC
    ┃      ┃        .
    ┃      ┗ CAB    .
A ━┫                .               
    ┃      ┏ BAC    .
    ┃      ┃        .
    ┗ BA ━╋ ACB   ┏ CBAD
            ┃       ┣ BADC
            ┗ CBA ━┫
                     ┣ ADCB
                     ┗ DCBA

1.硬件部份
一．系统BIOS初始化
当我们按下电源开关(POWER)时，电源开始供电,计算机的电源指示灯亮起.电源就开始向主板和其它设备供电，此时电压还没有完全稳定，主板控制芯片组会根据CMOS中的CPU主频设置向CPU发出一个Reset(重置)信号，让CPU内部自动恢复到初始状态，但CPU在此刻不会马上执行指令。当芯片组检测到电源已经开始稳定供电了（当然从不稳定到稳定的过程只是一瞬间的事情），它便撤去RESET信号（如果是手工按下计算机面板上的Reset按钮来重启机器，那么松开该按钮时芯片组就会撤去RESET信号），CPU马上从地址FFFF0H处执行一条跳转指令，从前面的介绍可知，这个地址实际上在系统 BIOS的地址范围内，无论是Award BIOS还是AMI BIOSCPU放在这里的只是一条跳转指令，跳到系统BIOS中真正的启动代码处。
二．POST(Power On Self Test，加电自检)。
系统BIOS首先要做的事情就是进行POST(Power On Self Test，加电自检)。POST的主要任务是检测系统中的一些关键设备电源、CPU芯片、BIOS芯片、中断控制器以及基本的64K内存和内存刷新电路等是否存在和能否正常工作，如内存和显卡等。POST过程进行得非常快，我们几乎无法感觉到它的存在．如果POST自检不成功系统的喇叭发出刺耳的警报声,具体的错误一般可以从警报声的长短和次数来判断.(小说明：为什么这时的错误要用声音来报警而不是在屏幕上显示呢，这是因为POST的检测过程在显示卡初始化之前，也就是说这时还是“黑屏”阶段，所以在POST的过程中发现了一些致命错误是无法在屏幕上显示出来的.)
三，显卡检测
自检通过后，系统BIOS将查找显示卡的BIOS，存放显示卡BIOS的ROM芯片的起始地址通常在C0000H处，系统BIOS找到显卡BIOS之后调用它的初始化代码，由显卡BIOS来完成显示卡的初始化．显示器开始有显示，BIOS将检查显示卡的BIOS，找到之后调用它的初始化代码，由显卡 BIOS找来完成显示卡的初始化。大多数显示卡在这个过程通常会在屏幕上显示出一些显示卡的信息，如生产厂商、图形芯片类型、显存容量等内容，这也就是我们开机看到的第一个画面了。如图1:

   四.CPU，内存检测
自此系统就具备了最基本的运行条件.可以对主板上的其它部分进行诊断和测试(例如CMOS错误）再发现故障时，屏幕上会有提示，但一般不死机，当查找完所有其他设备的BIOS之后，系统BIOS将显示它自己的启动画面，其中包括有系统BIOS的类型，序列号和版本号等内容，同?.聊蛔蟊咧猩辖腔岢鱿种靼逍畔⒋ 耄 ˙IOS的日期、主板芯片组型号、厂家的代码等。接着系统BIOS将检测CPU的类型和工作频率，并将结果显示在屏幕上；然后BIOS开始测试主机的内存容量，并在屏幕上显示内存测试数值。（就是大家所熟悉的屏幕上半部分那个飞速翻滚的内存计数器)当BIOS画面最下方出行＂DEL"的文字时就可以按下键盘上的＂DEL"键（按照你的主板说明按下相应的键）进行BIOS设置了．如图2：

四．标准硬件设备与即插即用设备检测
下一步BIOS将开始检测系统中安装的一些标准硬件设备：硬盘、CD-ROM、软驱、串行和并行接口等设备。标准设备检测完毕后，系统BIOS内部支持即插即用的代码将开始检测和配置系统中安装的即插即用设备，同时为该设备分配中断、DMA通道和I/O端口等资源，到此所有硬件都已经检测配置完毕．BIOS会重新清屏并在屏幕上方显示出一个系统配置表，其中简略地列出安装的各种标准硬件设备及相关工作参数。最后系统BIOS将更新 ESCD(Extended System Configuration Data，扩展系统配置数据)。（ESCD是系统BIOS用来与操作系统交换硬件配置信息的数据，这些数据被存放在CMOS中。通常ESCD数据只在系统硬件配置发生改变后才会进行更新，并不是每次启动都需要更新。ESCD数据更新完毕后，系统BIOS的启动代码将进行它的最后一项工作，即根据用户指定的启动顺序从软盘、硬盘或光驱启动．）
六。 硬盘引导
一．上述过程完毕了之后，首先BIOS检测硬盘并进行复位，然后根据用户在BIOS的设置来检查从哪一个设置引导系统，例如软驱，硬盘，光驱等，而其中最常用的就是硬盘引导了．从硬盘引导之后，BIOS把主引导记录读入内存，关将控制权交给主引导程序，检查分区表，寻找活动分区（这就是为什么在用 Fdisk分区时要设置活动分区了）找到之后再将控制权交给活动分区的引寻记录，由引寻记录来引导操作系统．若成功引导接着屏幕便出行系统启动的界面如 XP的标志画面,图3

可以按下F8键选择启模式．如不成功将会出现出错信息，例子：
如果硬盘上的分区表被破坏后，启动系统时往往会出现“Non-System disk or disk error，replace disk and press a key to reboot”（非系统盘或盘出错）、“Error Loading Operating System”（装入DOS引导记录错误）或者“No ROM Basic，System Halted”（不能进入ROM Basic，系统停止响应）就无法启动系统了．
为了照顾新手下面给出一下说明，请认真看：

硬盘主引导记录（MBR）：硬盘主引导记录区位于硬盘的首部，负责搜索硬盘可以启动的分区．对于DOS来说，它是由Fdisk生成的．主引导记录着从分区表中找到第一个活动分区，然后读取并执行这个活动分区的分区引导记录
活动分区：当我们在DOS用Fdisk命令硬盘分区时，一定要设一个主分区为活动分区，不然系统无法启动．一般来说活动分区就是我们平时用的系统盘C盘．
分区表（DPT)：分区表DPT则以80H或00H为开始标志，以55AAH为结束标志，位于主引导扇区的最末端。整个分区表决定了硬盘中的分区数量，每个分区的起始及终止扇区、大小以及是否为活动分区等。
活动分区的引寻记录：对于不同的系统，引导记录读取执行的文件是不一样的，对于DOS和WIN9X而言，分区引导记录执行＂IO．sys"
对于WIN2000\XP来说，则是由＂NTLDR"程序来执行的．

    以上介绍的便是计算机在打开电源开关（或按Reset键）进行冷启动时所要完成的各种初始化工作，如果我们在DOS下按Ctrl＋Alt＋Del组合键（或从Windows中选择重新启动计算机）来进行热启动，那么POST过程将被跳过去，直接从第三步开始，另外的检测CPU和内存测试也不会再进行。我们可以看到，无论是冷启动还是热启动，系统BIOS都一次又一次地重复进行着这些我们平时并不太注意的事情，然而正是这些单调的硬件检测步骤为我们能够正常使用电脑提供了基础。

２．软件部方（以XP系统为例说明）
注明：
要让Windows XP正确启动，在启动和系统分区中必须有以下文件：
Ntldr                位于系统分区根目录中
Boot.ini                位于系统分区根目录中
Ntdetect.com        位于系统分区根目录中
Ntoskrnl.exe          位于启动分区中的Windows\System32目录中
Hal.dll                位于启动分区中的Windows\System32目录中
注册表文件                位于启动分区中的Windows\System32 \Config\System目录中
设备驱动程序        位于启动分区中的Windows\System32 \Drivers目录中
如果计算机中还装有Win9X/Me，那么在系统分区根目录中必须有Bootsect.dos；如果计算机中有SCSI设备，系统分区根目录中还必须有Ntbootdd.sys。
1.系统启动引导阶段
Ntldr读取将boot.ini的内容，定位操作系统所在的启动分区。如果计算机中只有一个操作系统，Ntldr会自动执行下一步。如果计算机中有多个操作系统，那么这时会有一个选单让你选择你要启动的操作系统，当你选择Windows NT 4.0/2000/XP/2003时，Ntldr也会执行下一步；当你选择Windows 9X/Me时，Ntldr会把计算机的控制权交给Bootsect.dos.
检测和配置硬件阶段
启动Windows XP后(以XP说明），Ntldr启动ntdetect.com。ntdetect.com将收集计算机硬件信息列表并将列表返回到Ntldr，这样做的目的是便于以后将这些硬件信息加入到注册表HKEY_LOCAL_MACHINE下的hardware中。ntdetect.com的重要性在于在不兼容 ACPI（Advanced Configuration and Power Interface）的计算机中列举设备，这种情况下，设备资源是由硬件分配的。在兼容ACPI的计算机中，设备资源是由操作系统分配的。在这个过程中，ntdetect.com会查找Windows XP 创建的硬件配置文件。Windows XP会为桌面型电脑创建一个硬件配置文件，为移动型电脑创建两个硬件配置文件，用户也可以创建自己特定的硬件配置文件。硬件配置文件中没有的设备的驱动程序不会在Windows XP启动过程中加载。对于有多个硬件配置文件的计算机，用户可以选择是否在启动时显示硬件配置文件选单以便用户选择特定的硬件配置文件。
2.内核加载阶段
在这个阶段，ntldr首先加载称为Windows XP内核的ntokrnl.exe。这里，系统加载了Windows XP内核但是没有将它初始化。接着ntldr加载硬件抽象层（Hardware Abstraction Layer，hal.dll），然后，系统继续加载HKEY_LOCAL_MACHINE\SYSTEM键，ntldr读取 HKEY_LOCAL_MACHINE\SYSTEM\Select中的键值来决定哪一个ControlSet（熟悉注册表的朋友一定都发现在 HKEY_LOCAL_MACHINE\SYSTEM下有好几个ControlSet，比如ControlSet001，ControlSet002 ）将被加载。ControlSet中包含设备的驱动程序以及需要加载的服务。ntldr加载HKEY_LOCAL_MACHINE\SYSTEM \ControlSetXXX\Services\...（这里，ControlSetXXX指Select中选定的ControlSet，...指服务的名称）下start键值为0的最底层设备驱动。当作为ControlSet镜像的CurrentControlSet被加载时，ntldr将计算机的控制权交给Windows XP内核的ntokrnl.exe，初始化内核就开始了。
初始化内核开始的时候，彩色的Windows XP的logo以及进度条显示在屏幕中央，在这个阶段，系统完成了启动的4项任务：
1）内核使用在硬件检测时收集到的数据来创建HKEY_LOCAL_MACHINE\HARDWARE键。
2）内核通过复制HKEY_LOCAL_MACHINE\ SYSTEM \CurrentControlSet的值来创建了HKEY_LOCAL_MACHINE\ SYSTEM \Clone。Clone是计算机数据的备份，不包括启动中的改变，也不会被修改。
3）系统完成初始化以及加载设备驱动程序，内核初始化那些在加载内核阶段被加载的底层驱动程序，然后内核扫描 HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\...下start键值为1的设备驱动程序。这些设备驱动程序在加载的时候便完成初始化，如果有错误发生，内核使用ErrorControl键值来决定如何处理，值为3时，错误标志为危机/关键，系统初次遇到错误会以HKEY_LOCAL_MACHINE\SYSTEM\Select中LastKnownGood 所指的ControlSet重新启动，如果使用LastKnownGood ControlSet启动仍然产生错误，系统报告启动失败，错误信息将被显示，系统停止启动；值为2时错误情况为严重，系统启动失败并且以 LastKnownGood ControlSet重新启动，如果系统启动已经在使用LastKnownGood值，它会忽略错误并且继续启动；当值是1的时候错误为普通，系统会产生一个错误信息，但是会忽略这个错误并且继续启动；当值是0的时候忽略，系统不会显示任何错误信息而继续运行。
4）内核启动Session Manager（Smss.exe）。Session Manager的作用是启动Windows XP高级子系统以及服务，启动控制所有输入、输出设备以及访问显示器屏幕的Win32子系统以及Windows登陆进程（Winlogon.exe）。到这里，初始化内核就完成了。
3.登陆阶段
Winlogon.exe首先启动服务管理（Service Control Manager，Services.exe）和本地安全认证（Local Security Authority，Lsass.exe），同时显示Windows XP欢迎屏幕，这时候，系统还可能在后台继续初始化刚才没有完成的驱动程序。然后Winlogon会提示用户输入有效的用户名或密码（如果Windows XP中除了默认的administrator和隐藏帐户外只有一个用户帐户且没有密码，Windows XP会跳过这一步）。接着，服务管理最后执行以及扫描HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet \Servives来检查是否还有服务需要加载，服务管理查找start键值为2或更高的服务，服务按照start的值以及DependOnGroup和 DepandOnService的值来加载。
只有用户成功登陆到计算机后，Windows XP的启动才被认为是完成，在成功登陆后，系统拷贝HKEY_LOCAL_MACHINE\SYSTEM\Clone到LastKnownGood ControlSet，完成这一步骤后，系统才意味着已经成功引导了