±à¼ÍƼö: |
±¾ÎÄÖ÷ÒªÏêϸ½éÉÜÁ˰׺вâÊÔµÄÖ÷ҪĿµÄ¡¢·½·¨¡¢±ê×¼ÒÔ¼°°×ºÐ²âÊԵŤ¾ß£¬¾ßÌåÏêÇ飬Çë¹Ø×¢ÏÂÎÄ¡£
±¾ÎÄÀ´×ÔÓÚ²©¿ÍÔ°£¬ÓÉ»ðÁú¹ûÈí¼þAlice±à¼¡¢ÍƼö¡£ |
|
1 °×ºÐ²âÊԵĸÅÄî
°×ºÐ²âÊÔÒ²³Æ½á¹¹²âÊÔ»òÂß¼Çý¶¯²âÊÔ£¬ÊÇÒ»ÖÖ²âÊÔÓÃÀýÉè¼Æ·½·¨£¬Ëü´Ó³ÌÐòµÄ¿ØÖƽṹµ¼³ö²âÊÔÓÃÀý¡££¨²âÊÔÓÃÀýÓɲâÊÔÊäÈëÊý¾ÝÒÔ¼°ÓëÖ®¶ÔÓ¦µÄÊä³ö½á¹û×é³É¡££©
°×ºÐ²âÊÔʹÓñ»²âµ¥ÔªÄÚ²¿ÈçºÎ¹¤×÷µÄÐÅÏ¢£¬ÔÊÐí²âÊÔÈËÔ±¶Ô³ÌÐòÄÚ²¿Âß¼½á¹¹¼°ÓйØÐÅÏ¢À´Éè¼ÆºÍÑ¡Ôñ²âÊÔÓÃÀý£¬¶Ô³ÌÐòµÄÂ߼·¾¶½øÐвâÊÔ¡£»ùÓÚÒ»¸öÓ¦ÓôúÂëµÄÄÚ²¿Â߼֪ʶ£¬²âÊÔÊÇ»ùÓÚ¸²¸ÇÈ«²¿´úÂë¡¢·ÖÖ§¡¢Â·¾¶¡¢Ìõ¼þ¡£
2 °×ºÐ²âÊÔµÄÖ÷ҪĿµÄ
±£Ö¤Ò»¸öÄ£¿éÖеÄËùÓжÀÁ¢Â·¾¶ÖÁÉÙ±»Ö´ÐÐÒ»´Î£»
¶ÔËùÓеÄÂß¼Öµ¾ùÐèÒª²âÊÔÕæ¡¢¼ÙÁ½¸ö·ÖÖ§£»
ÔÚÉÏϱ߽缰¿É²Ù×÷·¶Î§ÄÚÔËÐÐËùÓÐÑ»·£»
¼ì²éÄÚ²¿Êý¾Ý½á¹¹ÒÔÈ·±£ÆäÓÐЧÐÔ¡£
3 ²âÊÔ¸²¸Ç±ê×¼
°×ºÐ·¨Ìص㣺ÒÔ³ÌÐòµÄÄÚ²¿Â߼Ϊ»ù´¡Éè¼Æ²âÊÔÓÃÀý£¬ËùÒÔÓÖ³ÆÎªÂß¼¸²¸Ç·¨¡£Ó¦Óð׺з¨Ê±£¬ÊÖÍ·±ØÐëÓгÌÐòµÄ¹æ¸ñ˵Ã÷ÒÔ¼°³ÌÐòÇåµ¥¡£
°×ºÐ·¨¿¼ÂǵÄÊDzâÊÔÓÃÀý¶Ô³ÌÐòÄÚ²¿Âß¼µÄ¸²¸Ç³Ì¶È¡£×î³¹µ×µÄ°×ºÐ·¨ÊǸ²¸Ç³ÌÐòÖеÄÿһÌõ·¾¶£¬µ«ÊÇÓÉÓÚ³ÌÐòÖÐÒ»°ãº¬ÓÐÑ»·£¬ËùÒÔ·¾¶µÄÊýÄ¿¼«´ó£¬ÒªÖ´ÐÐÿһÌõ·¾¶ÊDz»¿ÉÄܵģ¬Ö»ÄÜÏ£Íû¸²¸ÇµÄ³Ì¶È¾¡¿ÉÄܸßЩ¡£

ͼ1 ³ÌÐòÁ÷³Ìͼ
ͼ1°üÀ¨ÁËÒ»¸öÖ´Ðдï20´ÎµÄÑ»·¡£ÄÇôËüËù°üº¬µÄ²»Í¬Ö´Ðз¾¶Êý¸ß´ï520£¨£½1013£©Ìõ£¬ÈôÒª¶ÔËü½øÐÐÇî¾Ù²âÊÔ£¬¸²¸ÇËùÓеÄ·¾¶¡£¼Ùʹ²âÊÔ³ÌÐò¶ÔÿһÌõ·¾¶½øÐвâÊÔÐèÒª1ºÁÃ룬ͬ
Ñù¼Ù¶¨Ò»Ì칤×÷24Сʱ£¬Ò»Ä깤×÷365Ì죬 ÄÇôҪÏë°ÑÈçͼËùʾµÄС³ÌÐòµÄËùÓз¾¶²âÊÔÍ꣬ÔòÐèÒª3170Äê¡£
ΪÁ˺âÁ¿²âÊԵĸ²¸Ç³Ì¶È£¬ÐèÒª½¨Á¢Ò»Ð©±ê×¼£¬Ä¿Ç°³£ÓõÄһЩ¸²¸Ç±ê×¼´ÓµÍµ½¸ß·Ö±ðÊÇ£º
Óï¾ä¸²¸Ç£ºÊÇÒ»¸ö±È½ÏÈõµÄ²âÊÔ±ê×¼£¬ËüµÄº¬ÒåÊÇ£ºÑ¡Ôñ×ã¹»µÄ²âÊÔÓÃÀý£¬Ê¹µÃ³ÌÐòÖÐÿ¸öÓï¾äÖÁÉÙ¶¼Äܱ»Ö´ÐÐÒ»´Î¡£ËüÊÇ×îÈõµÄÂß¼¸²¸Ç£¬Ð§¹ûÓÐÏÞ£¬±ØÐëÓëÆäËü·½·¨½»»¥Ê¹Óá£
Åж¨¸²¸Ç£¨Ò²³ÆÎª·ÖÖ§¸²¸Ç£©£ºÖ´ÐÐ×ã¹»µÄ²âÊÔÓÃÀý£¬Ê¹µÃ³ÌÐòÖеÄÿһ¸ö·ÖÖ§ÖÁÉÙ¶¼Í¨¹ýÒ»´Î¡£Åж¨¸²¸ÇÖ»±ÈÓï¾ä¸²¸ÇÉÔǿһЩ£¬µ«Êµ¼ÊЧ¹û±íÃ÷£¬Ö»ÊÇÅж¨¸²¸Ç£¬»¹²»Äܱ£Ö¤Ò»¶¨Äܲé³öÔÚÅжϵÄÌõ¼þÖдæÔڵĴíÎó¡£Òò´Ë£¬»¹ÐèÒª¸üÇ¿µÄÂß¼¸²¸Ç×¼ÔòÈ¥¼ìÑéÅжÏÄÚ²¿Ìõ¼þ¡£
Ìõ¼þ¸²¸Ç£ºÖ´ÐÐ×ã¹»µÄ²âÊÔÓÃÀý£¬Ê¹³ÌÐòÖÐÿ¸öÅжϵÄÿ¸öÌõ¼þµÄÿ¸ö¿ÉÄÜȡֵÖÁÉÙÖ´ÐÐÒ»´Î£»Ìõ¼þ¸²¸ÇÉîÈëµ½Åж¨ÖеÄÿ¸öÌõ¼þ£¬µ«¿ÉÄܲ»ÄÜÂú×ãÅж¨¸²¸ÇµÄÒªÇó¡£
Åж¨/Ìõ¼þ¸²¸Ç£ºÖ´ÐÐ×ã¹»µÄ²âÊÔÓÃÀý£¬Ê¹µÃÅж¨ÖÐÿ¸öÌõ¼þÈ¡µ½¸÷ÖÖ¿ÉÄܵÄÖµ£¬²¢Ê¹Ã¿¸öÅж¨È¡µ½¸÷ÖÖ¿ÉÄܵĽá¹û¡£Åж¨/Ìõ¼þ¸²¸ÇÓÐȱÏÝ¡£´Ó±íÃæÉÏÀ´¿´£¬Ëü²âÊÔÁËËùÓÐÌõ¼þµÄȡֵ¡£µ«ÊÇÊÂʵ²¢·ÇÈç´Ë¡£ÍùÍùijЩÌõ¼þÑÚ¸ÇÁËÁíһЩÌõ¼þ¡£»áÒÅ©ijЩÌõ¼þȡֵ´íÎóµÄÇé¿ö¡£Îª³¹µ×µØ¼ì²éËùÓÐÌõ¼þµÄȡֵ£¬ÐèÒª½«Åж¨Óï¾äÖиø³öµÄ¸´ºÏÌõ¼þ±í´ïʽ½øÐзֽ⣬ÐγÉÓɶà¸ö»ù±¾Åж¨Ç¶Ì×µÄÁ÷³Ìͼ¡£ÕâÑù¾Í¿ÉÒÔÓÐЧµØ¼ì²éËùÓеÄÌõ¼þÊÇ·ñÕýÈ·ÁË¡£
Ìõ¼þ×éºÏ¸²¸Ç£ºÖ´ÐÐ×ã¹»µÄÀý×Ó£¬Ê¹µÃÿ¸öÅж¨ÖÐÌõ¼þµÄ¸÷ÖÖ¿ÉÄÜ×éºÏ¶¼ÖÁÉÙ³öÏÖÒ»´Î¡£ÕâÊÇÒ»ÖÖÏ൱ǿµÄ¸²¸Ç×¼Ôò£¬¿ÉÒÔÓÐЧµØ¼ì²é¸÷ÖÖ¿ÉÄܵÄÌõ¼þȡֵµÄ×éºÏÊÇ·ñÕýÈ·¡£Ëü²»µ«¿É¸²¸ÇËùÓÐÌõ¼þµÄ¿ÉÄÜȡֵµÄ×éºÏ£¬»¹¿É¸²¸ÇËùÓÐÅжϵĿÉÈ¡·ÖÖ§£¬µ«¿ÉÄÜÓеÄ·¾¶»áÒÅ©µô¡£²âÊÔ»¹²»ÍêÈ«¡£
4 °×ºÐ²âÊÔµÄÖ÷Òª·½·¨
Âß¼Çý¶¯²âÊÔ
Óï¾ä¸²¸Ç
Åж¨¸²¸Ç£¨·ÖÖ§¸²¸Ç£©
Ìõ¼þ¸²¸Ç
Åж¨/Ìõ¼þ¸²¸Ç
Ìõ¼þ×éºÏ¸²¸Ç
»ù±¾Â·¾¶²âÊÔ
Éè¼Æ×ã¹»¶àµÄ²âÊÔÓÃÀý£¬ÔËÐÐËù²â³ÌÐò£¬Òª¸²¸Ç³ÌÐòÖÐËùÓпÉÄܵÄ·¾¶¡£ÕâÊÇ×îÇ¿µÄ¸²¸Ç×¼Ôò¡£µ«ÔÚ·¾¶ÊýÄ¿ºÜ´óʱ£¬ÕæÕý×öµ½ÍêÈ«¸²¸ÇÊǺÜÀ§Äѵ쬱ØÐë°Ñ¸²¸Ç·¾¶ÊýĿѹËõµ½Ò»¶¨ÏÞ¶È¡£
4.1 Âß¼Çý¶¯²âÊÔ
4.1.1 Óï¾ä¸²¸Ç
³ÌÐò1ÈçÏ£º

ͼ2 ³ÌÐòÁ÷³Ìͼ
Ϊʹ³ÌÐòÖÐÿ¸öÓï¾äÖÁÉÙÖ´ÐÐÒ»´Î£¬Ö»ÐèÉè¼ÆÒ»¸öÄÜͨ¹ý·¾¶aceµÄÀý×ӾͿÉÒÔÁË£¬¾Í¿É´ïµ½¡°Óï¾ä¸²¸Ç¡±±ê×¼¡£ÀýÈçÑ¡ÔñÊäÈëÊý¾ÝΪ£º
A=2£¬B=0£¬X=3
ȱµã£º ´ÓÉÏÀý¿É¿´³ö£¬Óï¾ä¸²¸Çʵ¼ÊÉÏÊǺÜÈõµÄ
Èç¹ûµÚÒ»¸öÌõ¼þÓï¾äÖеÄAND´íÎ󵨱àд³ÉOR£¬ÉÏÃæµÄ²âÊÔÓÃÀýÊDz»ÄÜ·¢ÏÖÕâ¸ö´íÎóµÄ£»
ÓÖÈçµÚÈý¸öÌõ¼þÓï¾äÖÐX£¾1Îóд³ÉX£¾0£¬Õâ¸ö²âÊÔÓÃÀýÒ²²»Äܱ©Â¶Ëü£»
´ËÍâ£¬ÑØ×Å·¾¶abdÖ´ÐÐʱ£¬XµÄÖµÓ¦¸Ã±£³Ö²»±ä£¬Èç¹ûÕâÒ»·½ÃæÓдíÎó£¬ÉÏÊö²âÊÔÊý¾ÝÒ²²»ÄÜ·¢ÏÖËüÃÇ¡£
4.1.2 Åж¨¸²¸Ç£¨·ÖÖ§¸²¸Ç£©
¶Ô³ÌÐò1£¬Èç¹ûÉè¼ÆÁ½¸öÓÃÀý£¬Ê¹ËüÃÇÄÜͨ¹ý·¾¶aceºÍabd£¬»òÕßͨ¹ý·¾¶acdºÍabe£¬¾Í¿É´ïµ½¡°Åж¨¸²¸Ç¡±±ê×¼£¬Îª´Ë£¬¿ÉÒÔÑ¡ÔñÊäÈëÊý¾ÝΪ£º
A=3£¬B=0£¬X=1 (ÑØÂ·¾¶acdÖ´ÐÐ)£»
A=2£¬B=1£¬X=3(ÑØÂ·¾¶abeÖ´ÐÐ)
Óŵ㣺¡°·ÖÖ§¸²¸Ç¡±±È¡°Óï¾ä¸²¸Ç¡±Ñϸñ£¬ÒòΪÈç¹ûÿ¸ö·ÖÖ§¶¼Ö´ÐйýÁË£¬Ôòÿ¸öÓï¾äÒ²¾ÍÖ´ÐйýÁË¡£
ȱµã£ºµ«ÊÇ£¬¡°·ÖÖ§¸²¸Ç¡±»¹ÊǺܲ»¹»µÄ
Á½¸ö²âÊÔÓÃÀýδÄÜ¿¾Â¯µ½A<=1µÄÇé¿ö
Á½¸ö²âÊÔÓÃÀýδÄܼì²éÑØ×Å·¾¶abdÖ´ÐÐʱ£¬XµÄÖµÊÇ·ñ±£³Ö²»±ä¡£
4.1.3 Ìõ¼þ¸²¸Ç
Ò»¸öÅж¨ÖÐÍùÍù°üº¬ÁËÈô¸É¸öÌõ¼þ£¬Èç³ÌÐòÖУ¬Åж¨ (A£¾1) AND (B=0)°üº¬ÁËÁ½¸öÌõ¼þ£º A£¾1ÒÔ¼°
B=0£¬ËùÒÔ¿ÉÒý½øÒ»¸ö¸üÇ¿µÄ¸²¸Ç±ê×¼¡ª¡ª¡°Ìõ¼þ¸²¸Ç¡±¡£
³ÌÐò1ÓÐËĸöÌõ¼þ£º
A£¾1 ¡¢B=0¡¢A=2¡¢X£¾1
ΪÁË´ïµ½¡°Ìõ¼þ¸²¸Ç¡±±ê×¼£¬ÐèÒªÖ´ÐÐ×ã¹»µÄ²âÊÔÓÃÀýʹµÃÔÚaµãÓУº
A£¾1¡¢A¡Ü1¡¢B=0¡¢B¡Ù0
ÒÔ¼°ÔÚbµãÓУº
A=2¡¢A¡Ù2¡¢X£¾1¡¢X¡Ü1
ÏÖÔÚÖ»ÐèÉè¼ÆÒÔÏÂÁ½¸ö²âÊÔÓÃÀý¾Í¿ÉÂú×ãÕâÒ»±ê×¼£º
A=2£¬B=1£¬X=4 (ÑØÂ·¾¶abeÖ´ÐÐ)£»
A=1£¬B=0£¬X=1 (ÑØÂ·¾¶abdÖ´ÐÐ)¡£
Óŵ㣺¡°Ìõ¼þ¸²¸Ç¡±Í¨³£±È¡°·ÖÖ§¸²¸Ç¡±Ç¿£¬ÒòΪËüʹһ¸öÅж¨ÖеÄÿһ¸öÌõ¼þ¶¼È¡µ½ÁËÁ½¸ö²»Í¬µÄ½á¹û£¬¶øÅж¨¸²¸ÇÔò²»±£Ö¤ÕâÒ»µã¡£
ȱµã£º¡°Ìõ¼þ¸²¸Ç¡±²¢²»°üº¬¡°·ÖÖ§¸²¸Ç¡±£¬ÈçÁ½¸öÓÃÀýûÓÐÓи²¸ÇÅж¨£¨A>1 and B=0£©ÎªTrueµÄÇé¿ö
4.1.4 Åж¨/Ìõ¼þ¸²¸Ç
³ÌÐò1£¬ÒÔÏÂÓÃÀýÊÇÂú×ãÅж¨/Ìõ¼þ¸²¸Ç£º
A=2£¬B=0£¬X=4 (ÑØace·¾¶)
A=1£¬B=1£¬X=1 (ÑØabd·¾¶)
Óŵ㣺¼ÈÓС°Ìõ¼þ¸²¸Ç¡±£¬ÓÖÓС°Åж¨¸²¸Ç¡±
ȱµã£º·ÖÖ§/Ìõ¼þ¸²¸Ç´Ó±íÃæÀ´¿´£¬Ëü²âÊÔÁËËùÓÐÌõ¼þµÄȡֵ£¬µ«ÊÇʵ¼ÊÉÏijЩÌõ¼þÑÚ¸ÇÁËÁíһЩÌõ¼þ¡£
¶ÔÓÚµÚÒ»¸ö±í´ïʽ£¨A>1 and B=0£©Èç¹û£¨A£¾1£©Îª¼ÙÔòÒ»°ãµÄ±àÒëÆ÷²»ÔÚÅжÏÊÇ·ñB=0ÁË¡£
¶ÔÓÚµÚ¶þ¸ö±í´ïʽ£¨A=2 or X>1£©À´Ëµ£¬ÈôA=2²âÊÔ½á¹ûÎªÕæ£¬¾ÍÈÏΪ±í´ïʽµÄ½á¹ûÎªÕæ£¬Õâʱ²»ÔÙ¼ì²é£¨X>1£©Ìõ¼þÁË¡£
Òò´Ë£¬²ÉÓ÷ÖÖ§/Ìõ¼þ¸²¸Ç£¬Âß¼±í´ïʽÖеĴíÎó²»Ò»¶¨Äܹ»²é³öÀ´ÁË¡£
4.1.5 Ìõ¼þ×éºÏ¸²¸Ç
³ÌÐò1£¬ÒÔÏÂÓÃÀýÊÇÂú×ãÌõ¼þ×éºÏ¸²¸Ç£º
ÔÙ¿´³ÌÐò1£¬ÎÒÃÇÐèҪѡÔñÊʵ±µÄÓÃÀý£¬Ê¹µÃÏÂÃæ 8ÖÖÌõ¼þ×éºÏ¶¼Äܹ»³öÏÖ£º
1) A>1, B=0¡¡¡¡2) A>1, B¡Ù0¡¡¡¡3) A¡Ü1, B=0¡¡¡¡4) A¡Ü1,
B¡Ù0
5) A=2, X>1¡¡¡¡6) A=2, X¡Ü1¡¡¡¡7) A¡Ù2, X>1¡¡¡¡8) A¡Ù2,
X¡Ü1
5) ¡¢6) ¡¢7)¡¢8)ËÄÖÖÇé¿öÊǵڶþ¸ö IFÓï¾äµÄÌõ¼þ×éºÏ£¬¶øXµÄÖµÔÚ¸ÃÓï¾ä֮ǰÊÇÒª¾¹ý¼ÆËãµÄ£¬ËùÒÔ»¹±ØÐë¸ù¾Ý³ÌÐòµÄÂß¼ÍÆËã³öÔÚ³ÌÐòµÄÈë¿ÚµãXµÄÊäÈëÖµÓ¦ÊÇʲô¡£
ÏÂÃæÉè¼ÆµÄËĸöÓÃÀý¿ÉÒÔʹÉÏÊö 8ÖÖÌõ¼þ×éºÏÖÁÉÙ³öÏÖÒ»´Î£º
A=2£¬B=0£¬X=4 ʹ 1)¡¢5)Á½ÖÖÇé¿ö³öÏÖ (ÑØace·¾¶)£»
A=2£¬B=1£¬X=1 ʹ 2)¡¢6)Á½ÖÖÇé¿ö³öÏÖ (ÑØabd·¾¶)£»
A=1£¬B=0£¬X=2 ʹ 3)¡¢7)Á½ÖÖÇé¿ö³öÏÖ (ÑØabe·¾¶)£»
A=1£¬B=1£¬X=1 ʹ 4)¡¢8)Á½ÖÖÇé¿ö³öÏÖ (ÑØabd·¾¶)¡£
Óŵ㣺¼ÈÓС°Ìõ¼þ¸²¸Ç¡±£¬ÓÖÓС°Åж¨¸²¸Ç¡±£¬»¹ÓС°Ìõ¼þ×éºÏ¸²¸Ç¡±
ȱµã£ºÉÏÃæËĸöÀý×ÓËäÈ»Âú×ãÌõ¼þ×éºÏ¸²¸Ç£¬µ«²¢²»Äܸ²¸Ç³ÌÐòÖеÄÿһÌõ·¾¶£¬ÀýÈç·¾¶acd¾ÍûÓÐÖ´ÐÐ
4.1.6 ºÚºÐ·¨²¹³ä²âÊÔÓÃÀý
ͨ¹ýÇ°ÃæÂß¼Çý¶¯²âÊÔ·½·¨£¬¿ÉÒԵõ½Á½µã½áÂÛ£º
¡°Ìõ¼þ×éºÏ¸²¸Ç¡±±ê×¼±ÈÆäËû±ê×¼ÓÅÔ½¡£
¼´Ê¹´ïµ½ÈκÎÒ»ÖÖ¸²¸Ç±ê×¼£¬Æä²âÊÔЧ¹ûÈÔÈ»ÊDz»³¹µ×µÄ£¬ÎÒÃÇ»¹ÐèÒªÓÃÆäËûµÄ²âÊÔ·½·¨×÷²¹³ä¡£
Ò»¸ö²Î¿¼µÄºÚºÐ·¨²¹³ä²ßÂÔÊÇ£º
1) ÔÚÈκÎÇé¿ö϶¼ÐèʹÓñ߽çÖµ·ÖÎö(Õâ¸ö·½·¨Ó¦°üÀ¨¶ÔÊäÈëºÍÊä³öµÄ±ß½çÖµ½øÐзÖÎö)¡£
2) ±ØÒªµÄ»°£¬ÔÙÓõȼ۷ÖÀà·¨²¹³äһЩ²âÊÔÓÃÀý¡£
3) ÔÙÓôíÎóÍÆ²â·¨¸½¼Ó²âÊÔÓÃÀý¡£
4) ¼ì²éÉÏÊöÀý×ÓµÄÂß¼¸²¸Ç³Ì¶È£¬Èç¹ûδÄÜÂú×ãijЩ¸²¸Ç±ê×¼£¬ÔòÔÙÔö¼Ó×ã¹»µÄ²âÊÔÓÃÀý¡£
5) Èç¹û¹¦ÄÜ˵Ã÷Öк¬ÓÐÊäÈëÌõ¼þµÄ×éºÏÇé¿ö£¬ÔòÒ»¿ªÊ¼¾Í¿ÉÏÈÓÃÒò¹ûͼ(Åж¨±í)·¨¡£
4.2 ·¾¶²âÊÔ
·¾¶²âÊÔ¾ÍÊÇÉè¼Æ×ã¹»¶àµÄ²âÊÔÓÃÀý£¬¸²¸Ç±»²âÊÔ¶ÔÏóÖеÄËùÓпÉÄÜ·¾¶¡£
4.2.1 »ù±¾Â·¾¶²âÊÔ
³ÌÐò1ÊǺܼòµ¥µÄ³ÌÐòº¯Êý£¬Ö»ÓÐËÄÌõ·¾¶¡£µ«ÔÚʵ¼ùÖУ¬Ò»¸ö²»Ì«¸´ÔӵijÌÐò£¬Æä·¾¶¶¼ÊÇÒ»¸öÅÓ´óµÄÊý×Ö£¬ÒªÔÚ²âÊÔÖи²¸ÇËùÓеÄ·¾¶ÊDz»ÏÖʵµÄ¡£ÎªÁ˽â¾öÕâÒ»ÄÑÌ⣬ֻµÃ°Ñ¸²¸ÇµÄ·¾¶ÊýѹËõµ½Ò»¶¨ÏÞ¶ÈÄÚ£¬ÀýÈ磬³ÌÐòÖеÄÑ»·ÌåÖ»Ö´ÐÐÒ»´Î¡£
»ù±¾Â·¾¶²âÊÔ¾ÍÊÇÕâÑùÒ»ÖÖ²âÊÔ·½·¨£¬ËüÔÚ³ÌÐò¿ØÖÆÍ¼µÄ»ù´¡ÉÏ£¬Í¨¹ý·ÖÎö¿ØÖƹ¹ÔìµÄ»·Ðи´ÔÓÐÔ£¬µ¼³ö»ù±¾¿ÉÖ´Ðз¾¶¼¯ºÏ£¬´Ó¶øÉè¼Æ²âÊÔÓÃÀýµÄ·½·¨¡£Éè¼Æ³öµÄ²âÊÔÓÃÀýÒª±£Ö¤ÔÚ²âÊÔÖгÌÐòµÄÿһ¸ö¿ÉÖ´ÐÐÓï¾äÖÁÉÙÖ´ÐÐÒ»´Î¡£
ÔÚ³ÌÐò¿ØÖÆÁ÷ͼµÄ»ù´¡ÉÏ£¬Í¨¹ý·ÖÎö¿ØÖƹ¹ÔìµÄ»·Â·¸´ÔÓÐÔ£¬µ¼³ö»ù±¾¿ÉÖ´Ðз¾¶¼¯ºÏ£¬´Ó¶øÉè¼Æ²âÊÔÓÃÀý¡£°üÀ¨ÒÔÏÂ4¸ö²½ÖèºÍÒ»¸ö¹¤¾ß·½·¨£º
³ÌÐòµÄ¿ØÖÆÁ÷ͼ£ºÃèÊö³ÌÐò¿ØÖÆÁ÷µÄÒ»ÖÖͼʾ·½·¨¡£
³ÌÐòȦ¸´ÔÓ¶È£ºMcCabe¸´ÔÓÐÔ¶ÈÁ¿¡£´Ó³ÌÐòµÄ»·Â·¸´ÔÓÐԿɵ¼³ö³ÌÐò»ù±¾Â·¾¶¼¯ºÏÖеĶÀÁ¢Â·¾¶ÌõÊý£¬ÕâÊÇÈ·¶¨³ÌÐòÖÐÿ¸ö¿ÉÖ´ÐÐÓï¾äÖÁÉÙÖ´ÐÐÒ»´ÎËù±ØÐëµÄ²âÊÔÓÃÀýÊýÄ¿µÄÉϽ硣
µ¼³ö²âÊÔÓÃÀý£º¸ù¾ÝȦ¸´ÔӶȺͳÌÐò½á¹¹Éè¼ÆÓÃÀýÊý¾ÝÊäÈëºÍÔ¤ÆÚ½á¹û¡£
×¼±¸²âÊÔÓÃÀý£ºÈ·±£»ù±¾Â·¾¶¼¯ÖеÄÿһÌõ·¾¶µÄÖ´ÐС£
¹¤¾ß·½·¨£º
ͼÐξØÕó£ºÊÇÔÚ»ù±¾Â·¾¶²âÊÔÖÐÆð¸¨Öú×÷ÓõÄÈí¼þ¹¤¾ß£¬ÀûÓÃËü¿ÉÒÔʵÏÖ×Ô¶¯µØÈ·¶¨Ò»¸ö»ù±¾Â·¾¶¼¯¡£
1) ¿ØÖÆÁ÷ͼ
ÔÚ½éÉÜ»ù±¾Â·¾¶·½·¨Ö®Ç°£¬±ØÐëÏȽéÉÜÒ»ÖÖ¼òµ¥µÄ¿ØÖÆÁ÷±íʾ·½·¨£¬¼´Á÷ͼ¡£Á÷ͼÊǶԴý²âÊÔ³ÌÐò¹ý³Ì´¦ÀíµÄÒ»ÖÖ±íʾ¡£Á÷ͼʹÓÃÏÂÃæµÄ·ûºÅÃèÊöÂß¼¿ØÖÆÁ÷£¬Ã¿Ò»Öֽṹ»¯¹¹³ÉÔªËØÓÐÒ»¸öÏàÓ¦µÄÁ÷ͼ·ûºÅ¡£

ͼ3 Á÷ͼ·ûºÅ
Á÷ͼֻÓжþÖÖͼÐηûºÅ
ͼÖеÄÿһ¸öÔ²³ÆÎªÁ÷ͼµÄ½áµã£¬´ú±íÒ»Ìõ»ò¶àÌõÓï¾ä¡£
Á÷ͼÖеļýÍ·³ÆÎª±ß»òÁ¬½Ó£¬´ú±í¿ØÖÆÁ÷¡£
Èκιý³ÌÉè¼Æ¶¼Òª±»·Òë³É¿ØÖÆÁ÷ͼ¡£
ÔÚ½«³ÌÐòÁ÷³Ìͼ¼ò»¯³É¿ØÖÆÁ÷ͼʱ£¬Ó¦×¢Ò⣺
ÔÚÑ¡Ôñ»ò¶à·ÖÖ§½á¹¹ÖУ¬·ÖÖ§µÄ»ã¾Û´¦Ó¦ÓÐÒ»¸ö»ã¾Û½áµã¡£
±ßºÍ½áµãȦ¶¨µÄÇøÓò½Ð×öÇøÓò£¬µ±¶ÔÇøÓò¼ÆÊýʱ£¬Í¼ÐÎÍâµÄÇøÓòÒ²Ó¦¼ÇΪһ¸öÇøÓò¡£

ͼ4 ¿ØÖÆÁ÷ͼ
Èç¹ûÅжÏÖеÄÌõ¼þ±í´ïʽÊÇÓÉÒ»¸ö»ò¶à¸öÂß¼ÔËËã·û (OR, AND) Á¬½ÓµÄ¸´ºÏÌõ¼þ±í´ïʽ£¬ÔòÐèÒª¸ÄΪһϵÁÐÖ»Óе¥Ìõ¼þµÄǶÌ×µÄÅжϡ£

ͼ5 ³ÌÐò½á¹¹×ª»¯³ÉÁ÷ͼ
2) ¶ÀÁ¢Â·¾¶
¶ÀÁ¢Â·¾¶£ºÖÁÉÙÑØÒ»ÌõеıßÒÆ¶¯µÄ·¾¶
ͼ6 ¶ÀÁ¢Â·¾¶
¶ÔÒÔÉÏ·¾¶µÄ±éÀú£¬¾ÍÊÇÖÁÉÙÒ»´ÎµØÖ´ÐÐÁ˳ÌÐòÖеÄËùÓÐÓï¾ä
3) »ù±¾Â·¾¶²âÊÔ
µÚÒ»²½£º»³ö¿ØÖÆÁ÷ͼ
Á÷³ÌͼÓÃÀ´ÃèÊö³ÌÐò¿ØÖƽṹ¡£¿É½«Á÷³ÌͼӳÉäµ½Ò»¸öÏàÓ¦µÄÁ÷ͼ(¼ÙÉèÁ÷³ÌͼµÄÁâÐξö¶¨¿òÖв»°üº¬¸´ºÏÌõ¼þ)¡£
Á÷ͼÖÐÔ²£¬³ÆÎªÁ÷ͼµÄ½áµã£¬´ú±íÒ»¸ö»ò¶à¸öÓï¾ä¡£Ò»¸ö´¦Àí·½¿òÐòÁкÍÒ»¸öÁâÐξö²â¿ò¿É±»Ó³ÉäΪһ¸ö½áµã£»
Á÷ͼÖеļýÍ·£¬³ÆÎª±ß»òÁ¬½Ó£¬´ú±í¿ØÖÆÁ÷£¬ÀàËÆÓÚÁ÷³ÌͼÖеļýÍ·¡£Ò»Ìõ±ß±ØÐëÖÕÖ¹ÓÚÒ»¸ö½áµã£¬¼´Ê¹¸Ã½áµã²¢²»´ú±íÈκÎÓï¾ä(ÀýÈ磺if-else-then½á¹¹)£»
ÓɱߺͽáµãÏÞ¶¨µÄ·¶Î§³ÆÎªÇøÓò¡£¼ÆËãÇøÓòʱӦ°üÀ¨Í¼ÍⲿµÄ·¶Î§¡£

ͼ7 ³ÌÐòÁ÷³Ìͼ

ͼ8 ³ÌÐòÁ÷³ÌͼºÍ¶ÔÓ¦µÄ¿ØÖÆÁ÷ͼ
µÚ¶þ²½£º¼ÆËãȦ¸´ÔÓ¶È
Ȧ¸´ÔÓ¶ÈÊÇÒ»ÖÖΪ³ÌÐòÂß¼¸´ÔÓÐÔÌṩ¶¨Á¿²â¶ÈµÄÈí¼þ¶ÈÁ¿£¬½«¸Ã¶ÈÁ¿ÓÃÓÚ¼ÆËã³ÌÐòµÄ»ù±¾µÄ¶ÀÁ¢Â·¾¶ÊýÄ¿£¬ÎªÈ·±£ËùÓÐÓï¾äÖÁÉÙÖ´ÐÐÒ»´ÎµÄ²âÊÔÊýÁ¿µÄÉϽ硣
¶ÀÁ¢Â·¾¶±ØÐë°üº¬Ò»ÌõÔÚ¶¨Òå֮ǰ²»ÔøÓõ½µÄ±ß¡£
ÓÐÒÔÏÂÈýÖÖ·½·¨¼ÆËãȦ¸´ÔÓ¶È£º
Á÷ͼÖÐÇøÓòµÄÊýÁ¿¶ÔÓ¦ÓÚ»·Ð͵ĸ´ÔÓÐÔ£»
¸ø¶¨Á÷ͼGµÄȦ¸´ÔÓ¶ÈV(G)£¬¶¨ÒåΪV(G)=E-N+2£¬EÊÇÁ÷ͼÖбߵÄÊýÁ¿£¬NÊÇÁ÷ͼÖнáµãµÄÊýÁ¿£»
¸ø¶¨Á÷ͼGµÄȦ¸´ÔÓ¶ÈV(G)£¬¶¨ÒåΪV(G)=P+1£¬PÊÇÁ÷ͼGÖÐÅж¨½áµãµÄÊýÁ¿¡£
µÚÈý²½£ºµ¼³ö²âÊÔÓÃÀý
¸ù¾ÝÉÏÃæµÄ¼ÆËã·½·¨£¬¿ÉµÃ³öËĸö¶ÀÁ¢µÄ·¾¶¡£(Ò»Ìõ¶ÀÁ¢Â·¾¶ÊÇÖ¸£¬ºÍÆäËûµÄ¶ÀÁ¢Â·¾¶Ïà±È£¬ÖÁÉÙÒýÈëÒ»¸öд¦ÀíÓï¾ä»òÒ»¸öÐÂÅжϵijÌÐòͨ·¡£V(G)ÖµÕýºÃµÈÓڸóÌÐòµÄ¶ÀÁ¢Â·¾¶µÄÌõÊý¡£)
·¾¶1£º4-14
·¾¶2£º4-6-7-14
·¾¶3£º4-6-8-10-13-4-14
·¾¶4£º4-6-8-11-13-4-14
µÚËIJ½£º×¼±¸²âÊÔÓÃÀý
ΪÁËÈ·±£»ù±¾Â·¾¶¼¯ÖеÄÿһÌõ·¾¶µÄÖ´ÐУ¬¸ù¾ÝÅжϽáµã¸ø³öµÄÌõ¼þ£¬Ñ¡ÔñÊʵ±µÄÊý¾ÝÒÔ±£Ö¤Ä³Ò»Ìõ·¾¶¿ÉÒÔ±»²âÊÔµ½£¬Âú×ãÉÏÃæÀý×Ó»ù±¾Â·¾¶¼¯µÄ²âÊÔÓÃÀýÊÇ£º
·¾¶1£º4-14
ÊäÈëÊý¾Ý£ºiRecordNum£½0£¬»òÕßÈ¡iRecordNum<0µÄijһ¸öÖµ¡¡¡¡Ô¤ÆÚ½á¹û£ºx£½0
·¾¶2£º4-6-7-14
ÊäÈëÊý¾Ý£ºiRecordNum£½1,iType£½0¡¡¡¡Ô¤ÆÚ½á¹û£ºx£½2
·¾¶3£º4-6-8-10-13-4-14
ÊäÈëÊý¾Ý£ºiRecordNum£½1,iType£½1¡¡¡¡Ô¤ÆÚ½á¹û£ºx£½10
·¾¶4£º4-6-8-11-13-4-14
ÊäÈëÊý¾Ý£ºiRecordNum£½1,iType£½2¡¡¡¡Ô¤ÆÚ½á¹û£ºx£½20
±ØÐë×¢Ò⣬һЩ¶ÀÁ¢µÄ·¾¶£¬ÍùÍù²»ÊÇÍêÈ«¹ÂÁ¢µÄ£¬ÓÐʱËüÊdzÌÐòÕý³£µÄ¿ØÖÆÁ÷µÄÒ»²¿·Ö£¬Õâʱ£¬ÕâЩ·¾¶µÄ²âÊÔ¿ÉÒÔÊÇÁíÒ»Ìõ·¾¶²âÊÔµÄÒ»²¿·Ö¡£
4) ¹¤¾ß·½·¨£ºÍ¼ÐξØÕó
µ¼³ö¿ØÖÆÁ÷ͼºÍ¾ö¶¨»ù±¾²âÊÔ·¾¶µÄ¹ý³Ì¾ùÐèÒª»úе»¯£¬ÎªÁË¿ª·¢¸¨Öú»ù±¾Â·¾¶²âÊÔµÄÈí¼þ¹¤¾ß£¬³ÆÎªÍ¼ÐξØÕó(graph
matrix)µÄÊý¾Ý½á¹¹ºÜÓÐÓá£
ÀûÓÃͼÐξØÕó¿ÉÒÔʵÏÖ×Ô¶¯µØÈ·¶¨Ò»¸ö»ù±¾Â·¾¶¼¯¡£Ò»¸öͼÐξØÕóÊÇÒ»¸ö·½Õó
ÆäÐÐ/ÁÐÊý¿ØÖÆÁ÷ͼÖеĽáµãÊý£¬Ã¿ÐкÍÿÁÐÒÀ´Î¶ÔÓ¦µ½Ò»¸ö±»±êʶµÄ½áµã£¬
¾ØÕóÔªËØ¶ÔÓ¦µ½½áµã¼äµÄÁ¬½Ó£¨¼´±ß£©¡£
¶Ôÿ¸ö¾ØÕóÏî¼ÓÈëÁ¬½ÓȨֵ(link weight)£¬Í¼¾ØÕó¾Í¿ÉÒÔÓÃÓÚÔÚ²âÊÔÖÐÆÀ¹À³ÌÐòµÄ¿ØÖƽṹ£¬Á¬½ÓȨֵΪ¿ØÖÆÁ÷ÌṩÁËÁíÍâµÄÐÅÏ¢¡£×î¼òµ¥Çé¿öÏ£¬Á¬½ÓȨֵÊÇ
1(´æÔÚÁ¬½Ó)»ò0(²»´æÔÚÁ¬½Ó)£¬µ«ÊÇ£¬Á¬½ÓȨֵ¿ÉÒÔ¸³Óè¸üÓÐȤµÄÊôÐÔ£º
Ö´ÐÐÁ¬½Ó(±ß)µÄ¸ÅÂÊ¡£
´©Ô½Á¬½ÓµÄ´¦Àíʱ¼ä¡£
´©Ô½Á¬½ÓʱËùÐèµÄÄÚ´æ¡£
´©Ô½Á¬½ÓʱËùÐèµÄ×ÊÔ´¡£

ͼ9 ͼÐξØÕó
Á¬½ÓȨΪ¡°1¡±±íʾ´æÔÚÒ»¸öÁ¬½Ó£¬ÔÚͼÖÐÈç¹ûÒ»ÐÐÓÐÁ½¸ö»ò¸ü¶àµÄÔªËØ¡°1¡±£¬ÔòÕâÐÐËù´ú±íµÄ½áµãÒ»¶¨ÊÇÒ»¸öÅж¨½áµã£¬Í¨¹ýÁ¬½Ó¾ØÕóÖÐÓÐÁ½¸öÒÔÉÏ£¨°üÀ¨Á½¸ö£©ÔªËØÎª¡°1¡±µÄ¸öÊý£¬¾Í¿ÉÒԵõ½È·¶¨¸ÃͼȦ¸´ÔӶȵÄÁíÒ»ÖÖËã·¨¡£
5 ¿ØÖƽṹ²âÊÔµÄÆäËû±äÖÖ
Ç°ÃæËùÊöµÄ»ù±¾Â·¾¶²âÊÔ¼¼ÊõÊÇ¿ØÖƽṹ²âÊÔ¼¼ÊõÖ®Ò»¡£¾¡¹Ü»ù±¾Â·¾¶²âÊÔ¼òµ¥¸ßЧ£¬µ«ÊÇ£¬Æä±¾Éí²¢²»³ä·Ö¡£ÏÂÃæÌÖÂÛ¿ØÖƽṹ²âÊÔµÄÆäËû±äÖÖ£¬ÕâЩ²âÊÔ¸²¸Ç²¢Ìá¸ßÁ˰׺вâÊÔµÄÖÊÁ¿¡£°üÀ¨£º
Ìõ¼þ²âÊÔ
Êý¾ÝÁ÷²âÊÔ £¨ÂÔ£©
Ñ»·²âÊÔ¡£
5.1 Ìõ¼þ²âÊÔ
Ìõ¼þ²âÊÔ·½·¨×¢ÖØÓÚ²âÊÔ³ÌÐòÖеÄÌõ¼þ¡£ÊǼì²é³ÌÐòÄ£¿éÖÐËù°üº¬Âß¼Ìõ¼þµÄ²âÊÔÓÃÀýÉè¼Æ·½·¨¡£
5.1.1 Ìõ¼þ
³ÌÐòÖеÄÌõ¼þ·ÖΪ¼òµ¥Ìõ¼þºÍ¸´ºÏÌõ¼þ¡£
¼òµ¥Ìõ¼þÊÇÒ»¸ö²¼¶û±äÁ¿»òÒ»¸ö¿ÉÄÜ´øÓÐNOT(¡°£¡¡±)²Ù×÷·ûµÄ¹ØÏµ±í´ïʽ¡£¹ØÏµ±í´ïʽµÄÐÎʽÈ磺
E1£¼¹ØÏµ²Ù×÷·û£¾E2
ÆäÖÐE1ºÍE2ÊÇËãÊõ±í´ïʽ£¬¶ø£¼¹ØÏµ²Ù×÷·û£¾ÊÇÏÂÁÐÖ®Ò»£º¡°£¼¡±¡¢¡°¡Ü¡±¡¢¡°=¡±¡¢¡°¡Ù¡±(¡°£¡=¡±)¡¢¡°£¾¡±¡¢»ò¡°¡Ý¡±¡£
¸´ºÏÌõ¼þÓɼòµ¥Ìõ¼þͨ¹ýÂß¼ÔËËã·û£¨AND¡¢OR¡¢NOT£©ºÍÀ¨ºÅÁ¬½Ó¶ø³É£¬²»º¬¹ØÏµ±í´ïʽµÄÌõ¼þ³ÆÎª²¼¶û±í´ïʽ¡£
ËùÒÔÌõ¼þµÄ³É·ÖÀàÐͰüÀ¨£º²¼¶û²Ù×÷·û¡¢²¼¶û±äÁ¿¡¢²¼¶ûÀ¨»¡(À¨×¡¼òµ¥»ò¸´ÔÓÌõ¼þ)¡¢¹ØÏµ²Ù×÷·û¡¢ËãÊõ±í´ïʽ¡£
5.1.2 Ìõ¼þ²âÊÔµÄÄ¿µÄ
Ìõ¼þ²âÊÔÊDzâÊÔ³ÌÐòÌõ¼þ´íÎóºÍ³ÌÐòµÄÆäËû´íÎó¡£Èç¹û³ÌÐòµÄ²âÊÔ¼¯Äܹ»ÓÐЧµØ¼ì²â³ÌÐòÖеÄÌõ¼þ´íÎó£¬Ôò¸Ã²âÊÔ¼¯¿ÉÄÜÒ²»áÓÐЧµØ¼ì²â³ÌÐòÖÐµÄÆäËû´íÎó¡£´ËÍ⣬Èç¹û²âÊÔ²ßÂÔ¶Ô¼ì²âÌõ¼þ´íÎóÓÐЧ£¬ÔòËüÒ²¿ÉÄÜÓÐЧµØ¼ì²â³ÌÐò´íÎó¡£
5.1.3 Ìõ¼þ²âÊÔ²ßÂÔ
1) Çî¾Ù²âÊÔ£¨Ìõ¼þ×éºÏ£©
ÓÐn¸ö±äÁ¿µÄ²¼¶û±í´ïʽÐèÒª2n¸ö¿ÉÄܵIJâÊÔ(n£¾0)¡£ÕâÖÖ²ßÂÔ¿ÉÒÔ·¢ÏÖ²¼¶û²Ù×÷·û¡¢±äÁ¿ºÍÀ¨»¡µÄ´íÎ󣬵«ÊÇÖ»ÓÐÔÚnºÜСʱʵÓá£
2) ·ÖÖ§²âÊÔ
·ÖÖ§²âÊÔ¿ÉÄÜÊÇ×î¼òµ¥µÄÌõ¼þ²âÊÔ²ßÂÔ£¬ËüÊÇÕæ¼Ù·ÖÖ§±ØÐëÖÁÉÙÖ´ÐÐÒ»´ÎµÄ·¾¶²ßÂÔ£¬¶ÔÓÚ¸´ºÏÌõ¼þC£¬CµÄÕæ·ÖÖ§ºÍ¼Ù·ÖÖ§ÒÔ¼°CÖеÄÿ¸ö¼òµ¥Ìõ¼þ¶¼ÐèÒªÖÁÉÙÖ´ÐÐÒ»´Î¡£
Óò²âÊÔÊǶÔÓÚ´óÓÚ¡¢Ð¡Óں͵ÈÓÚÖµµÄ²âÊÔ·¾¶²ßÂÔ¡£Óò²âÊÔÒªÇó´ÓÓÐÀí±í´ïʽÖе¼³öÈý¸ö»òËĸö²âÊÔ£¬ÓÐÀí±í´ïʽµÄÐÎʽÈ磺
E1£¼¹ØÏµ²Ù×÷·û£¾E2
ÐèÒªÈý¸ö²âÊÔ·Ö±ðÓÃÓÚ¼ÆËãE1µÄÖµÊÇ´óÓÚ¡¢µÈÓÚ»òСÓÚE2µÄÖµ¡£Èç¹û£¼¹ØÏµ²Ù×÷·û£¾´íÎ󣬶øE1ºÍE2ÕýÈ·£¬ÔòÕâÈý¸ö²âÊÔÄܹ»·¢ÏÖ¹ØÏµËã×ӵĴíÎó¡£ÎªÁË·¢ÏÖE1ºÍE2µÄ´íÎ󣬼ÆËãE1СÓÚ»ò´óÓÚE2µÄ²âÊÔӦʹÁ½¸öÖµ¼äµÄ²î±ð¾¡¿ÉÄÜС¡£
3) BRO(branch and relational) ²âÊÔ
Èç¹ûÔÚÒ»¸öÅж¨µÄ¸´ºÏÌõ¼þ±í´ïʽÖÐÿ¸ö²¼¶û±äÁ¿ºÍ¹ØÏµÔËËã·û×î¶àÖ»³öÏÖÒ»´Î£¬¶øÇÒûÓй«¹²±äÁ¿£¬Ó¦ÓÃÒ»ÖÖ³ÆÖ®ÎªBRO£¨·ÖÖ§Óë¹ØÏµÔËËã·û£©µÄ²âÊÔ·¨¿ÉÒÔ·¢ÏÖ¶à¸ö²¼¶ûÔËËã·û»ò¹ØÏµÔËËã·û´í£¬ÒÔ¼°ÆäËû´íÎó¡£
BRO²ßÂÔÒýÈëÌõ¼þÔ¼ÊøµÄ¸ÅÄî¡£ÉèÓÐn¸ö¼òµ¥Ìõ¼þµÄ¸´ºÏÌõ¼þC£¬ÆäÌõ¼þÔ¼ÊøÎªD= (D1£¬D2£¬¡£¬Dn)
£¬ÆäÖÐDi(0£¼i¡Ün)ÊÇÌõ¼þCÖеÚi¸ö¼òµ¥Ìõ¼þµÄÊä³öÔ¼Êø¡£Èç¹ûÔÚCµÄÖ´Ðйý³ÌÖУ¬Æäÿ¸ö¼òµ¥Ìõ¼þµÄÊä³ö¶¼Âú×ãDÖжÔÓ¦µÄÔ¼Êø£¬Ôò³ÆÌõ¼þCµÄÌõ¼þÔ¼ÊøDÓÉCµÄÖ´ÐÐËù¸²¸Ç¡£¶ÔÓÚ²¼¶û±äÁ¿»ò²¼¶û±í´ïʽB£¬BµÄÊä³öÔ¼Êø±ØÐëÊÇÕæ£¨t£©»ò¼Ù£¨f£©£»¶ÔÓÚ¹ØÏµ±í´ïʽ£¬ÆäÊä³öÔ¼ÊøÎª·ûºÅ>¡¢=¡¢<
¡£
5.2 Ñ»·²âÊÔ
Ñ»·²âÊÔÊÇÒ»Öְ׺вâÊÔ¼¼Êõ£¬×¢ÖØÓÚÑ»·¹¹ÔìµÄÓÐЧÐÔ¡£
ÓÐËÄÖÖÑ»·£º¼òµ¥Ñ»·£¬´®½Ó(Á¬Ëø)Ñ»·£¬Ç¶Ì×Ñ»·¡¢²»¹æÔòÑ»·¡£

ͼ10 Ñ»·½á¹¹
¶ÔÓÚ¼òµ¥Ñ»·£¬²âÊÔÓ¦°üÀ¨ÒÔϼ¸ÖÖ£¬ÆäÖеÄn±íʾѻ·ÔÊÐíµÄ×î´ó´ÎÊý¡£
Áã´ÎÑ»·£º´ÓÑ»·Èë¿ÚÖ±½ÓÌøµ½Ñ»·³ö¿Ú¡£
Ò»´ÎÑ»·£º²éÕÒÑ»·³õʼֵ·½ÃæµÄ´íÎó¡£
¶þ´ÎÑ»·£º¼ì²éÔÚ¶à´ÎÑ»·Ê±²ÅÄܱ©Â¶µÄ´íÎó¡£
m´ÎÑ»·£º´ËʱµÄm£¼n£¬Ò²ÊǼì²éÔÚ¶à´ÎÑ»·Ê±²ÅÄܱ©Â¶µÄ´íÎó¡£
n(×î´ó)´ÎÊýÑ»·¡¢n+1(±È×î´ó´ÎÊý¶àÒ»)´ÎµÄÑ»·¡¢n-1(±È×î´ó´ÎÊýÉÙÒ»)´ÎµÄÑ»·¡£
¶ÔÓÚǶÌ×Ñ»·£¬²»Äܽ«¼òµ¥Ñ»·µÄ²âÊÔ·½·¨¼òµ¥µØÀ©´óµ½Ç¶Ì×Ñ»·£¬ÒòΪ¿ÉÄܵIJâÊÔÊýÄ¿½«ËæÇ¶Ìײã´ÎµÄÔö¼Ó³Ê¼¸ºÎ±¶ÊýÔö³¤¡£Õâ¿ÉÄܵ¼ÖÂÒ»¸öÌìÎÄÊý×ֵIJâÊÔÊýÄ¿¡£ÏÂÃæÊÇÒ»ÖÖÓÐÖúÓÚ¼õÉÙ²âÊÔÊýÄ¿µÄ²âÊÔ·½·¨¡£
´Ó×îÄÚ²ãÑ»·¿ªÊ¼£¬ÉèÖÃËùÓÐÆäËû²ãµÄÑ»·Îª×îСֵ£»
1.¶Ô×îÄÚ²ãÑ»·×ö¼òµ¥Ñ»·µÄÈ«²¿²âÊÔ¡£²âÊÔʱ±£³ÖËùÓÐÍâ²ãÑ»·µÄÑ»·±äÁ¿Îª×îСֵ¡£ÁíÍ⣬¶ÔÔ½½çÖµºÍ·Ç·¨Öµ×öÀàËÆµÄ²âÊÔ¡£
2.Öð²½ÍâÍÆ£¬¶ÔÆäÍâÃæÒ»²ãÑ»·½øÐвâÊÔ¡£²âÊÔʱ±£³ÖËùÓÐÍâ²ãÑ»·µÄÑ»·±äÁ¿È¡×îСֵ£¬ËùÓÐÆäËüǶÌ×ÄÚ²ãÑ»·µÄÑ»·±äÁ¿È¡¡°µäÐÍ¡±Öµ¡£
3.·´¸´½øÐУ¬Ö±µ½ËùÓи÷²ãÑ»·²âÊÔÍê±Ï¡£
4.¶ÔÈ«²¿¸÷²ãÑ»·Í¬Ê±È¡×îСѻ·´ÎÊý£¬»òÕßͬʱȡ×î´óÑ»·´ÎÊý¡£¶ÔÓÚºóÒ»ÖÖ²âÊÔ£¬ÓÉÓÚ²âÊÔÁ¿Ì«´ó£¬ÐèÈËΪָ¶¨×î´óÑ»·´ÎÊý¡£
¶ÔÓÚ´®½ÓÑ»·£¬ÒªÇø±ðÁ½ÖÖÇé¿ö¡£
Èç¹û¸÷¸öÑ»·»¥Ïà¶ÀÁ¢£¬Ôò´®½ÓÑ»·¿ÉÒÔÓÃÓë¼òµ¥Ñ»·ÏàͬµÄ·½·¨½øÐвâÊÔ¡£
Èç¹ûÓÐÁ½¸öÑ»·´¦ÓÚ´®½Ó״̬£¬¶øÇ°Ò»¸öÑ»·µÄÑ»·±äÁ¿µÄÖµÊǺóÒ»¸öÑ»·µÄ³õÖµ¡£ÔòÕ⼸¸öÑ»·²»ÊÇ»¥Ïà¶ÀÁ¢µÄ£¬ÔòÐèҪʹÓòâÊÔǶÌ×Ñ»·µÄ°ì·¨À´´¦Àí¡£
¶ÔÓڷǽṹѻ·£¬²»ÄܲâÊÔ£¬Ó¦ÖØÐÂÉè¼ÆÑ»·½á¹¹£¬Ê¹Ö®³ÉΪÆäËüÑ»··½Ê½£¬È»ºóÔÙ½øÐвâÊÔ¡£
6 ÃæÏò¶ÔÏóµÄ°×ºÐ²âÊÔ
¶ÔOOÈí¼þµÄÀà²âÊÔÏ൱ÓÚ´«Í³Èí¼þµÄµ¥Ôª²âÊÔ¡£ºÍ´«Í³Èí¼þµÄµ¥Ôª²âÊÔ²»Í¬£¬ËûÍùÍù¹Ø×¢Ä£¿éµÄË㷨ϸ½ÚºÍÄ£¿é½Ó¿Ú¼äÁ÷¶¯µÄÊý¾Ý£¬OOÈí¼þµÄÀà²âÊÔÊÇÓÉ·â×°ÔÚÀàÖеIJÙ×÷ºÍÀàµÄ״̬ÐÐΪËùÇý¶¯µÄ¡£OOÈí¼þ²âÊÔµÄÌØµã£º
ÒòΪÊôÐԺͲÙ×÷ÊDZ»·â×°µÄ£¬¶ÔÀàÖ®Íâ²Ù×÷µÄ²âÊÔͨ³£ÊÇͽÀ͵ġ£·âװʹ¶Ô¶ÔÏóµÄ״̬¿ìÕÕÄÑÓÚ»ñµÃ¡£
¼Ì³ÐÒ²¸ø²âÊÔ´øÀ´ÁËÄѶȣ¬¼´Ê¹Êdz¹µ×¸´Óõ쬶Ôÿ¸öеÄʹÓÃÓï¾³Ò²ÐèÒªÖØÐ²âÊÔ¡£
¶àÖØ¼Ì³Ð¸üÔö¼ÓÁËÐèÒª²âÊÔµÄÓï¾³µÄÊýÁ¿£¬Ê¹²âÊÔ½øÒ»²½¸´ÔÓ»¯¡£Èç¹û´Ó³¬Àർ³öµÄ²âÊÔÓÃÀý±»ÓÃÓÚÏàͬµÄÎÊÌâÓò£¬ÓпÉÄܶԳ¬Àർ³öµÄ²âÊÔÓÃÀý¼¯¿ÉÒÔÓÃÓÚ×ÓÀàµÄ²âÊÔ£¬È»¶ø£¬Èç¹û×ÓÀà±»ÓÃÓÚÍêÈ«²»Í¬µÄÓï¾³£¬Ôò³¬ÀàµÄ²âÊÔÓÃÀý½«Ã»Óжà´óÓÃ;£¬±ØÐëÉè¼ÆÐµIJâÊÔÓÃÀý¼¯¡£
6.1 Àà²âÊÔ·½Ê½
Àà²âÊÔÒ»°ãÓÐÁ½ÖÖÖ÷ÒªµÄ·½Ê½£º
¹¦ÄÜÐÔ²âÊԺͽṹÐÔ²âÊÔ£¬¼´¶ÔÓ¦ÓÚ´«Í³½á¹¹»¯Èí¼þµÄºÚºÐ²âÊԺͰ׺вâÊÔ£º
¹¦ÄÜÐÔ²âÊÔÒÔÀàµÄ¹æ¸ñ˵Ã÷Ϊ»ù´¡£¬ËüÖ÷Òª¼ì²éÀàÊÇ·ñ·ûºÏÆä¹æ¸ñ˵Ã÷µÄÒªÇó¡£ÀýÈ磬¶ÔÓÚStackÀ࣬¼´¼ì²éËüµÄ²Ù×÷ÊÇ·ñÂú×ãLIFO¹æÔò£»
½á¹¹ÐÔ²âÊÔÔò´Ó³ÌÐò³ö·¢£¬ËüÐèÒª¿¼ÂÇÆäÖеĴúÂëÊÇ·ñÕýÈ·£¬Í¬ÑùÊÇStackÀ࣬¾ÍÒª¼ì²éÆäÖдúÂëÊÇ·ñ¶¯×÷ÕýÈ·ÇÒÖÁÉÙÖ´ÐйýÒ»´Î¡£
6.1.1 ½á¹¹ÐÔ²âÊÔ
½á¹¹ÐÔ²âÊÔ¶ÔÀàÖеķ½·¨½øÐвâÊÔ£¬Ëü°ÑÀà×÷Ϊһ¸öµ¥ÔªÀ´½øÐвâÊÔ¡£²âÊÔ·ÖΪÁ½²ã£º
µÚÒ»²ã¿¼ÂÇÀàÖи÷¶ÀÁ¢·½·¨µÄ´úÂ룻
µÚ¶þ²ã¿¼ÂÇ·½·¨Ö®¼äµÄÏ໥×÷Óá£
ÿ¸ö·½·¨µÄ²âÊÔÒªÇóÄÜÕë¶ÔÆäËùÓеÄÊäÈëÇé¿ö£¬µ«ÕâÑù»¹²»¹»£¬Ö»ÓжÔÕâЩ·½·¨Ö®¼äµÄ½Ó¿ÚÒ²×öͬÑù²âÊÔ£¬²ÅÄÜÈÏΪ²âÊÔÊÇÍêÕûµÄ¡£
¶ÔÓÚÒ»¸öÀàµÄ²âÊÔÒª±£Ö¤ÀàÔÚÆä״̬µÄ´ú±í¼¯ÉÏÄܹ»ÕýÈ·¹¤×÷£¬¹¹Ô캯ÊýµÄ²ÎÊýÑ¡ÔñÒÔ¼°ÏûÏ¢ÐòÁеÄÑ¡Ôñ¶¼ÒªÂú×ãÕâÒ»×¼Ôò¡£Òò´Ë£¬ÔÚÕâÁ½¸ö²»Í¬µÄ²âÊÔ²ã´ÎÉÏÓ¦·Ö±ð×öµ½£º
·½·¨µÄµ¥¶À²âÊÔ£º½á¹¹ÐÔ²âÊԵĵÚÒ»²ãÊÇ¿¼ÂǸ÷¶ÀÁ¢µÄ·½·¨£¬Õâ¿ÉÒÔÓë¹ý³ÌµÄ²âÊÔ²ÉÓÃͬÑùµÄ·½·¨£¬Á½ÕßÖ®¼ä×î´óµÄ²î±ðÔÚÓÚ·½·¨¸Ä±äÁËËüËùÔÚʵÀýµÄ״̬£¬Õâ¾ÍҪȡµÃÒþ²ØµÄ״̬ÐÅÏ¢À´¹ÀËã²âÊԵĽá¹û£¬´«¸øÆäËü¶ÔÏóµÄÏûÏ¢±»ºöÂÔ£¬¶øÒÔ×®À´´úÌæ£¬²¢¸ù¾ÝËù´«µÄÏûÏ¢·µ»ØÏàÓ¦µÄÖµ£¬²âÊÔÊý¾ÝÒªÇóÄÜÍêÈ«¸²¸ÇÀàÖдúÂ룬¿ÉÒÔÓô«Í³µÄ²âÊÔ¼¼ÊõÀ´»ñÈ¡¡£
·½·¨µÄ×ۺϲâÊÔ£ºµÚ¶þ²ãÒª¿¼ÂÇÒ»¸ö·½·¨µ÷Óñ¾¶ÔÏóÀàÖÐµÄÆäËü·½·¨ºÍ´ÓÒ»¸öÀàÏòÆäËüÀà·¢ËÍÐÅÏ¢µÄÇé¿ö¡£µ¥¶À²âÊÔÒ»¸ö·½·¨Ê±£¬Ö»¿¼ÂÇÆä±¾ÉíÖ´ÐеÄÇé¿ö¡£¶øÃ»Óп¼ÂǶ¯×÷µÄ˳ÐòÎÊÌ⣬²âÊÔÓÃÀýÖмÓÈëÁ˼¤·¢ÕâЩµ÷ÓõÄÐÅÏ¢£¬ÒÔ¼ì²éËüÃÇÊÇ·ñÕýÈ·ÔËÐÐÁ˶ÔÓÚͬһÀàÖз½·¨Ö®¼äµÄµ÷Óã¬Ò»°ãÖ»ÐèÒª¼«ÉÙÉõÖÁ²»Óø½¼ÓÊý¾Ý£¬ÒòΪ·½·¨¶¼ÊǶÔÀà½øÐдæÈ¡£¬¹ÊÕâÒ»Àà²âÊÔµÄ×¼ÔòÊÇÒªÇó±éÀúÀàµÄËùÓÐÖ÷Ҫ״̬¡£
7 °×ºÐ²âÊÔ¹¤¾ß
ÄÚ´æ×ÊԴй©¼ì²é£ºNumegaÖеÄbouncechecker,RationalµÄPurifyµÈ£»
´úÂ븲¸ÇÂʼì²é£ºNumegaÖеÄtruecoverage,RationalµÄPurecoverage£¬Telelogic¹«Ë¾µÄlogiscope,Macabe¹«Ë¾µÄMacabeµÈ£»
¿ªÔ´¸²¸ÇÂʲâÊÔÈí¼þgCovµÈ¡£
8 ×ܽá
8.1 °×ºÐ²âÊÔµÄÖ÷Òª·½·¨µÄÓÅȱµã

×¢Ò⣺
»ù±¾Â·¾¶²âÊÔÒ²ÄÜÈ·±£¸²¸ÇÌõ¼þ£¬ÒòΪ£ºÈç¹ûÅжÏÖеÄÌõ¼þ±í´ïʽÊÇÓÉÒ»¸ö»ò¶à¸öÂß¼ÔËËã·û (OR, AND)
Á¬½ÓµÄ¸´ºÏÌõ¼þ±í´ïʽ£¬ÔòÐèÒª¸ÄΪһϵÁÐÖ»Óе¥Ìõ¼þµÄǶÌ×µÄÅжϼûͼ5¡£
µ«»ù±¾Â·¾¶²âÊÔÎÞ·¨È·±£¸²¸ÇÌõ¼þ×éºÏ£¬ÒòΪ£ºÈç¹ûÅжÏÖеÄÌõ¼þ±í´ïʽÊÇÓÉÒ»¸ö»ò¶à¸öÂß¼ÔËËã·û (OR,
AND) Á¬½ÓµÄ¸´ºÏÌõ¼þ±í´ïʽ£¬ÈôÊÇORÁ¬½ÓµÄǰһ¸ö±í´ïʽ·µ»ØÎªTrue£¬¾Í²»»á¿¼ÂǺóÒ»¸ö±í´ïʽ£»ÈôÊÇANDÁ¬½ÓµÄǰһ¸ö±í´ïʽ·µ»ØÎªFalse£¬¾Í²»»á¿¼ÂǺóÒ»¸ö±í´ïʽ£»
8.2 Çî¾Ù·¾¶²âÊԵľÖÏÞÐÔ
¡°°×ºÐ¡±·¨È«ÃæÁ˽â³ÌÐòÄÚ²¿Âß¼½á¹¹¡¢¶ÔËùÓÐÂ߼·¾¶½øÐвâÊÔ¡£¡°°×ºÐ¡±·¨ÊÇÇî¾Ù·¾¶²âÊÔ¡£ÔÚʹÓÃÕâÒ»·½°¸Ê±£¬²âÊÔÕß±ØÐë¼ì²é³ÌÐòµÄÄÚ²¿½á¹¹£¬´Ó¼ì²é³ÌÐòµÄÂß¼×ÅÊÖ£¬µÃ³ö²âÊÔÊý¾Ý¡£¹á´©³ÌÐòµÄ¶ÀÁ¢Â·¾¶ÊýÊÇÌìÎÄÊý×Ö¡£µ«¼´Ê¹Ã¿Ìõ·¾¶¶¼²âÊÔÁËÈÔÈ»¿ÉÄÜÓдíÎó£º
µÚÒ»¡¢Çî¾Ù·¾¶²âÊÔ¾ö²»Äܲé³ö³ÌÐòÎ¥·´ÁËÉè¼Æ¹æ·¶£¬¼´³ÌÐò±¾ÉíÊǸö´íÎóµÄ³ÌÐò£»
µÚ¶þ¡¢Çî¾Ù·¾¶²âÊÔ²»¿ÉÄܲé³ö³ÌÐòÖÐÒòÒÅ©·¾¶¶ø³ö´í¡£
µÚÈý¡¢Çî¾Ù·¾¶²âÊÔ¿ÉÄÜ·¢ÏÖ²»ÁËһЩÓëÊý¾ÝÏà¹ØµÄ´íÎó¡£ |