信息學(xué)奧賽講義

信息學(xué)奧賽講義信息學(xué)奧賽講義信息學(xué)奧賽講義信息學(xué)奧賽簡(jiǎn)介青少年信息學(xué)（計(jì)算機(jī)）奧林匹克競(jìng)賽（早期稱(chēng)為青少年計(jì)算機(jī)程序設(shè)計(jì)競(jìng)賽）是旨在廣大青少年中普及計(jì)算機(jī)教育，推廣計(jì)算機(jī)應(yīng)用的一項(xiàng)學(xué)科性競(jìng)賽活動(dòng)。全國(guó)從1984年開(kāi)始舉辦全國(guó)性競(jìng)賽。而自從1989年我國(guó)參加第一屆國(guó)際信息學(xué)奧林匹克（InternationalOlympiadinInformatics,簡(jiǎn)稱(chēng)IOI）以來(lái)，全國(guó)青少年計(jì)算機(jī)程序設(shè)計(jì)競(jìng)賽也更名為全國(guó)青少年信息學(xué)（計(jì)算機(jī)）奧林匹克（NationalOlympiadinInformatics,簡(jiǎn)稱(chēng)NOIP）。及此相應(yīng)，各省青少年計(jì)算機(jī)競(jìng)賽更名為各省青少年信息學(xué)奧林匹克競(jìng)賽。從而形成了從省──全國(guó)──國(guó)際相銜接的系列性活動(dòng)。全國(guó)信息學(xué)奧林匹克競(jìng)賽活動(dòng)擔(dān)負(fù)著選拔優(yōu)秀學(xué)生參加國(guó)際學(xué)科奧林匹克競(jìng)賽任務(wù)，它是經(jīng)國(guó)家教委批準(zhǔn)，中國(guó)科協(xié)具體領(lǐng)導(dǎo)，由中國(guó)計(jì)算機(jī)學(xué)會(huì)主辦的。聯(lián)賽命題宗旨

全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽（NOIP）是一項(xiàng)面向全國(guó)青少年的信息學(xué)競(jìng)賽和普及活動(dòng)，旨在向那些在中學(xué)階段學(xué)習(xí)的青少年普及計(jì)算機(jī)科學(xué)知識(shí)；給學(xué)校的信息技術(shù)教育課程提供動(dòng)力和新的思路；給那些有才華的學(xué)生提供相互交流和學(xué)習(xí)的機(jī)會(huì)；通過(guò)競(jìng)賽和相關(guān)的活動(dòng)培養(yǎng)和選拔優(yōu)秀的計(jì)算機(jī)人才。

競(jìng)賽的目的是為了在更高層次上推動(dòng)普及。本競(jìng)賽及其相關(guān)活動(dòng)遵循開(kāi)放性原則，任何有條件和有興趣的學(xué)校和個(gè)人，都可以在業(yè)余時(shí)間自愿參加。本活動(dòng)不和現(xiàn)行的學(xué)校教學(xué)相沖突，也不列入教學(xué)計(jì)劃，是課外性質(zhì)的因材施教活動(dòng)。參加者可為初高中學(xué)生或其他中等專(zhuān)業(yè)學(xué)校的青少年。

普及的內(nèi)容涉及

．計(jì)算機(jī)的基本組成；

．計(jì)算機(jī)工作的基本原理；

．計(jì)算機(jī)程序設(shè)計(jì)的基本方法；

．至少一門(mén)高級(jí)程序設(shè)計(jì)語(yǔ)言；

．程序設(shè)計(jì)中常用的數(shù)據(jù)結(jié)構(gòu)。

普及的重點(diǎn)是根據(jù)中學(xué)生的特點(diǎn)，培養(yǎng)學(xué)生學(xué)習(xí)計(jì)算機(jī)的興趣，使得他們對(duì)信息技術(shù)的一些本質(zhì)和核心的東西有更多的了解，提高他們創(chuàng)造性地運(yùn)用程序設(shè)計(jì)知識(shí)解決實(shí)際問(wèn)題的能力。對(duì)學(xué)生的能力培養(yǎng)注重

．想象力及創(chuàng)造力；

．對(duì)問(wèn)題的理解和分析能力；

．?dāng)?shù)學(xué)能力和邏輯思維能力；

．對(duì)客觀(guān)問(wèn)題和主觀(guān)思維的口頭和書(shū)面表達(dá)能力；

．人文精神。包括及人的溝通和理解能力，團(tuán)隊(duì)精神及合作能力，恒心和毅力，審美能力等。競(jìng)賽形式和成績(jī)?cè)u(píng)定

聯(lián)賽分兩個(gè)年齡組：初中組和高中組。每組競(jìng)賽分兩輪：初試和復(fù)試。

．初試形式為筆試，側(cè)重考察學(xué)生的計(jì)算機(jī)基礎(chǔ)知識(shí)和編程的基本能力，并對(duì)知識(shí)面的廣度進(jìn)行測(cè)試。程序設(shè)計(jì)的描述語(yǔ)言采用Pascal或Basic。各省市初試成績(jī)?cè)诒举悈^(qū)前百分之十五的學(xué)生進(jìn)入復(fù)賽，其分?jǐn)?shù)不計(jì)入復(fù)賽的成績(jī)。初賽時(shí)間為10月的最后一個(gè)星期六下午2:30-4:30舉行。

．復(fù)試形式為上機(jī)，側(cè)重考察學(xué)生對(duì)問(wèn)題的分析理解能力，數(shù)學(xué)抽象能力，駕馭編程語(yǔ)言的能力和編程技巧、想象力和創(chuàng)造性等。程序設(shè)計(jì)語(yǔ)言可采用Pascal、Basic、C/C++或Java。各省市競(jìng)賽的等第獎(jiǎng)在復(fù)試的優(yōu)勝者中產(chǎn)生。時(shí)間為3小時(shí)。只進(jìn)行一試，約在當(dāng)年的11月的最后一個(gè)周六進(jìn)行。競(jìng)賽形式和成績(jī)?cè)u(píng)定試題形式

每次聯(lián)賽的試題分四組：初中組初試賽題；初中組復(fù)試賽題；高中組初試賽題；高中組復(fù)試賽題。其中，初中組初試賽題和高中組初試賽題類(lèi)型相同，初中組復(fù)試賽題和高中組復(fù)試賽題類(lèi)型相同，但初中組和高中組的題目不完全相同，高中組難度略高；以體現(xiàn)年齡特點(diǎn)和層次要求。

．初試：初試全部為筆試，滿(mǎn)分100分。試題由四部分組成：

1、選擇題：共20題，每題1．5分，共30分。每題有5個(gè)備選方案；前10個(gè)題為單選題門(mén)每題有且只有一個(gè)正確答案），后10題為復(fù)選題（即每題有1至5個(gè)正確答案，只有全部選對(duì)才得分）。試題內(nèi)容包括計(jì)算機(jī)基本組成及原理、計(jì)算機(jī)基本操作、信息科技及人類(lèi)社會(huì)發(fā)展的關(guān)系等等。

2、問(wèn)題求解題：共2題，每題5分，共10分。試題給出一個(gè)敘述較為簡(jiǎn)單的問(wèn)題，要求學(xué)生對(duì)問(wèn)題進(jìn)行分析，找到一個(gè)合適的算法，并推算出問(wèn)題的解。答案以字符串方式給出，考生給出的答案及標(biāo)準(zhǔn)答案的字符串相同，則得分；否則不得分。

3、程序閱讀理解題：共4題，每題8分，共32分。題目給出一段程序（沒(méi)有關(guān)于程序功能的說(shuō)明），有時(shí)也會(huì)給出程序的輸入，要求考生通過(guò)閱讀理解該段程序給出程序的輸出。輸出以字符串的形式給出，如果及標(biāo)準(zhǔn)答案一致，則得分；否則不得分。

4、程序完善題：共2題，每題14分，共28分。題目給出一段關(guān)于程序功能的文字說(shuō)明，然后給出一段程序代碼，在代碼中略去了若干個(gè)語(yǔ)句并在這些位置給出空格，要求考生根據(jù)程序的功能說(shuō)明和代碼的上下文，填出被略去的語(yǔ)句。填對(duì)的，則得分；否則不得分。

．復(fù)試：復(fù)試的題型和形式向全國(guó)信息學(xué)奧賽（NOI）靠攏，全部為上機(jī)編程題，但難度略低。復(fù)試為決出競(jìng)賽成績(jī)的最后一個(gè)環(huán)節(jié)。題目包括4道題，每題100分，共計(jì)400分。難度有易有難，既考慮普及面，又考慮選拔的梯度要求。每一道試題包括：題目、問(wèn)題描述、樣例說(shuō)明（輸入、輸出及必要的說(shuō)明）。測(cè)試時(shí)，測(cè)試程序?yàn)槊康李}提供了十組測(cè)試數(shù)據(jù)，考生程序每答對(duì)一組得10分；累計(jì)分即為該道題的得分。試題形式考試內(nèi)容主要包括：計(jì)算機(jī)發(fā)展史、計(jì)算機(jī)組成、計(jì)算機(jī)基本原理、計(jì)算機(jī)程序設(shè)計(jì)、計(jì)算機(jī)日常應(yīng)用等。要求考生掌握至少一門(mén)高級(jí)程序設(shè)計(jì)語(yǔ)言（詳見(jiàn)競(jìng)賽大綱）。為了保持競(jìng)賽內(nèi)容的相對(duì)連續(xù)性，試題涵蓋的知識(shí)點(diǎn)和題型至少6O％應(yīng)出現(xiàn)在普及類(lèi)的參考書(shū)目中，其余內(nèi)容可能超出該范圍。

為了考核學(xué)生的基礎(chǔ)知識(shí)、綜合應(yīng)用能力，激發(fā)學(xué)生的求知欲和創(chuàng)新思維，體現(xiàn)“及時(shí)俱進(jìn)”的特點(diǎn)，競(jìng)賽題型在保持大綱相對(duì)穩(wěn)定、優(yōu)秀學(xué)生可能接受和理解的基礎(chǔ)上，按照下述趨勢(shì)適當(dāng)變化

1、增大及課內(nèi)知識(shí)結(jié)合的緊密度；

2、增大解題方法的多樣性和靈活程度；

3、增大開(kāi)放性試題的比例。試題的知識(shí)范圍計(jì)算機(jī)基礎(chǔ)知識(shí)計(jì)算機(jī)的誕生和發(fā)展

計(jì)算機(jī)的特點(diǎn)

計(jì)算機(jī)在現(xiàn)代社會(huì)中應(yīng)用

計(jì)算機(jī)的基本組成及其相互聯(lián)系

計(jì)算機(jī)的工作原理

計(jì)算機(jī)中的數(shù)的表示

計(jì)算機(jī)信息安全基礎(chǔ)知識(shí)

計(jì)算機(jī)軟件知識(shí)

實(shí)例11、美籍匈牙利數(shù)學(xué)家馮·諾依曼對(duì)計(jì)算機(jī)科學(xué)發(fā)展所做出的貢獻(xiàn)是（

）。

提出理想計(jì)算機(jī)的數(shù)學(xué)模型，成為計(jì)算機(jī)科學(xué)的理論基礎(chǔ)。

是世界上第一個(gè)編寫(xiě)計(jì)算機(jī)程序的人。

提出存儲(chǔ)程序工作原理，并設(shè)計(jì)出第一臺(tái)具有存儲(chǔ)程序功能的計(jì)算機(jī)EDVAC。

采用集成電路作為計(jì)算機(jī)的主要功能部件。

指出計(jì)算機(jī)性能將以每?jī)赡攴环乃俣认蚯鞍l(fā)展。

（第十屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題普及組Pascal語(yǔ)言）2、(2004)10+(32)16的結(jié)果是（

）。

(2036)10B.(2054)16C.(4006)10D.(100000000110)2E.(2036)16

（第十屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題普及組Pascal語(yǔ)言）cc實(shí)例23、圖靈(AlanTuring)是(

)。

A)美國(guó)人

B)英國(guó)人C)德國(guó)人D)匈牙利人E)法國(guó)人

（第九屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題普及組Pascal語(yǔ)言）4、第一個(gè)給計(jì)算機(jī)寫(xiě)程序的人是()。

AlanMathisonTuring

AdaLovelace

JohnvonNeumann

JohnMcCarthy

EdsgerWybeDijkstra

（第九屆全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽初賽試題普及組Pascal語(yǔ)言）BB是英國(guó)著名詩(shī)人拜倫的女兒及計(jì)算機(jī)相關(guān)的幾個(gè)重要人物艾倫·圖靈（AlanTuring）英國(guó)科學(xué)家，他是計(jì)算機(jī)人工智能技術(shù)的鼻祖。1937年他提出了能思考的計(jì)算機(jī)——圖靈機(jī)的概念，推進(jìn)了計(jì)算機(jī)理論的發(fā)展。圖靈機(jī)模型是一種抽象計(jì)算模型，用來(lái)精確定義可計(jì)算函數(shù)，是實(shí)現(xiàn)機(jī)器人的最基本的一個(gè)理論模型。1950年，艾倫·圖靈發(fā)表題為《計(jì)算機(jī)能思考嗎》的論文，設(shè)計(jì)了著名的圖靈測(cè)驗(yàn)，解決了如何判定機(jī)器人是否具有同人類(lèi)相等的智力的問(wèn)題。馮·諾依曼（JohnVonNeumann）1945年，他寫(xiě)了一篇題為《關(guān)于離散變量自動(dòng)電子計(jì)算機(jī)的草案》的論文，第一次提出了在數(shù)字計(jì)算機(jī)內(nèi)部的存儲(chǔ)器中存放程序的概念。這成為所有現(xiàn)代計(jì)算機(jī)的基礎(chǔ)理論，被稱(chēng)為“馮·諾依曼結(jié)構(gòu)”。如今，各式各樣的電腦無(wú)論看起來(lái)差別多大，實(shí)質(zhì)上絕大多數(shù)是屬于馮·諾依曼結(jié)構(gòu)的。及計(jì)算機(jī)相關(guān)的幾個(gè)重要人物高登·摩爾（GordonMoore）“每過(guò)18個(gè)月，計(jì)算機(jī)芯片依賴(lài)的集成電路由于內(nèi)部晶體管數(shù)量的幾何級(jí)數(shù)的增長(zhǎng)，而使性能幾乎提高一倍，同時(shí)集成電路的價(jià)格也恰好減少為原來(lái)的一半?！边@就是計(jì)算機(jī)界著名的摩爾定律，他的發(fā)明人就是高登·摩爾。1968年他及羅伯特·諾伊斯一起率領(lǐng)一群工程師創(chuàng)建了一家叫集成電子的公司，簡(jiǎn)稱(chēng)“Intel”，這就是當(dāng)今名震世界的英特爾公司。法國(guó)人帕斯卡于17世紀(jì)制造出的一種機(jī)械式加法機(jī)，是世界上第一臺(tái)機(jī)械式計(jì)算機(jī)。算盤(pán)是人類(lèi)最早的手動(dòng)計(jì)算工具，機(jī)械式計(jì)算機(jī)是在此之后出現(xiàn)的一種用機(jī)械技術(shù)來(lái)實(shí)現(xiàn)數(shù)學(xué)運(yùn)算的計(jì)算工具。CPU的發(fā)展歷史CPU(CentralProcessingUnit)，被稱(chēng)呼為中心處理器或者M(jìn)icroprocessor微處理器。CPU是計(jì)算機(jī)的核心，其重要性好比心臟對(duì)于人一樣。實(shí)際上，處理器的作用和大腦更相似，因?yàn)樗?fù)責(zé)處理、運(yùn)算計(jì)算機(jī)內(nèi)部的所有數(shù)據(jù)，而主板芯片組則更像是心臟，它控制著數(shù)據(jù)的交換。CPU的種類(lèi)決定了你使用的操作系統(tǒng)和相應(yīng)的軟件，CPU的速度決定了你的計(jì)算機(jī)有多強(qiáng)大，當(dāng)然越快、越新的CPU會(huì)花掉你更多的錢(qián)。

CPU從最初發(fā)展至今已經(jīng)有二十多年的歷史了，這期間，按照其處理信息的字長(zhǎng)，CPU可以分為：四位微處理器、八位微處理器、十六位微處理器、三十二位微處理器以及六十四位微處理器等等。

CPU的發(fā)展歷史1978年6月，Intel推出4.77MHz的8086微處理器，標(biāo)志著第三代微處理器問(wèn)世。它采用16位寄存器、16位數(shù)據(jù)總線(xiàn)和29000個(gè)3微米技術(shù)的晶體管1985年10月，Intel推出16MHz80386DX微處理器(最高33MHz主頻)，可以直接訪(fǎng)問(wèn)4G字節(jié)的內(nèi)存,并具有異常處理機(jī)制;虛擬86模式可以同時(shí)模擬多個(gè)8086處理器來(lái)加強(qiáng)多任務(wù)處理能力。80386的廣泛應(yīng)用,將PC機(jī)從16位時(shí)代帶入了32位時(shí)代。此外它還具有比80286更多的指令集。發(fā)布時(shí)，80386的最快速版本的主頻為20MHz，具備6.0MIPs，包含275,000個(gè)晶體管。1993年3月22日：全面超越486的新一代586CPU問(wèn)世，為了擺脫486時(shí)代微處理器名稱(chēng)混亂的困擾，英特爾公司把自己的新一代產(chǎn)品命名為Pentium(奔騰)以區(qū)別AMD和Cyrix的產(chǎn)品。2000年11月21日，Intel在全球同步發(fā)布了其最新一代的微處理器—Pentium4（奔騰4）。

Pentium4系統(tǒng)總線(xiàn)僅為100Mhz，并且也是64位數(shù)據(jù)寬度

CPU的主要性能指標(biāo)

主頻即CPU的時(shí)鐘頻率(CPUClockSpeed)，這是我們最關(guān)心的，我們所說(shuō)的3.2GHz、2.0GHz等就是指它，一般說(shuō)來(lái)，主頻越高，CPU的速度就越快，整機(jī)的就越高。

FSB前端總線(xiàn)即CPU的外部時(shí)鐘頻率，由電腦主板提供，以前一般是133MHz，目前Intel公司最新的芯片組i925XE芯片組使用1066MHz的FSB。

內(nèi)部緩存（L1Cache）封閉在CPU芯片內(nèi)部的高速緩存，用于暫時(shí)存儲(chǔ)CPU運(yùn)算時(shí)的部分指令和數(shù)據(jù)，存取速度及CPU主頻一致，L1緩存的容量單位一般為KB。L1緩存越大，CPU工作時(shí)及存取速度較慢的L2緩存和內(nèi)存間交換數(shù)據(jù)的次數(shù)越少，相對(duì)電腦的運(yùn)算速度可以提高。外部緩存（L2Cache）以CPU主頻的一半速度運(yùn)行CPU的主要性能指標(biāo)CPU(中央處理器)是電腦的核心，作為系統(tǒng)的心臟，CPU的檔次決定了整臺(tái)機(jī)器的處理水平，其性能的高低直接影響全局。電腦處理數(shù)據(jù)的能力和速度主要取決于CPU。通常用位長(zhǎng)和主頻評(píng)價(jià)CPU的能力和速度，如PⅡ300CPU能處理位長(zhǎng)為32位的二進(jìn)制數(shù)據(jù)，主頻為300MHz。

1、主頻、倍頻、外頻：主頻也就是CPU的時(shí)鐘頻率，英文全稱(chēng)是CPUClockSpeed，簡(jiǎn)單地說(shuō)也就是CPU運(yùn)算時(shí)的工作頻率。一般說(shuō)來(lái)，主頻越高，一個(gè)時(shí)鐘周期內(nèi)完成的指令數(shù)也越多，當(dāng)然CPU的速度也就越快了。不過(guò)由于各種各樣的CPU它們的內(nèi)部結(jié)構(gòu)也不盡相同，所以并非所有的時(shí)鐘頻率相同的CPU的性能都一樣。至于外頻就是系統(tǒng)總線(xiàn)的工作頻率；而倍頻則是指CPU外頻及主頻相差的倍數(shù)。三者是有十分密切的關(guān)系的：主頻=外頻×倍頻。存儲(chǔ)器及分類(lèi)一般我們存放在外存（磁盤(pán)或各種存儲(chǔ)介質(zhì)）上的資料都要通過(guò)內(nèi)存，再進(jìn)入CPU進(jìn)行處理。所以及內(nèi)存之間的通道——內(nèi)存總線(xiàn)的速度對(duì)整個(gè)系統(tǒng)性能就顯得很重要了，由于內(nèi)存和CPU之間的運(yùn)行速度或多或少會(huì)有差異，因此便出現(xiàn)了二級(jí)緩存，來(lái)協(xié)調(diào)兩者之間的差異，而內(nèi)存總線(xiàn)速度就是指CPU及二級(jí)（L2）高速緩存和內(nèi)存之間的通信速度。內(nèi)存儲(chǔ)器：簡(jiǎn)稱(chēng)內(nèi)存，用于存放當(dāng)前待處理的信息和常用信息的半導(dǎo)體芯片。容量不大，但存取迅速。內(nèi)存包括RAM、ROM和Cache。1、RAM：RAM(隨機(jī)存取存儲(chǔ)器)是電腦的主存儲(chǔ)器，人們習(xí)慣將RAM稱(chēng)為內(nèi)存。RAM的最大特點(diǎn)是關(guān)機(jī)或斷電數(shù)據(jù)便會(huì)丟失。內(nèi)存越大的電腦，能同時(shí)處理的信息量越大。我們用刷新時(shí)間評(píng)價(jià)RAM的性能，單位為ns(納秒)，刷新時(shí)間越小存取速度越快。586電腦常用RAM有EDORAM和SDRAM，存儲(chǔ)器芯片安裝在手指寬的條形電路板上，稱(chēng)之為內(nèi)存條。內(nèi)存條安裝在主板上的內(nèi)存條插槽中。按內(nèi)存條及主板的連接方式有30線(xiàn)、72線(xiàn)和168線(xiàn)之分。目前裝機(jī)常用168線(xiàn)、刷新時(shí)間為10ns、容量為32M(或64M)的SDRAM內(nèi)存條。

2、Cache：Cache(高速緩沖存儲(chǔ)器)是位于CPU及主內(nèi)存間的一種容量較小但速度很高的存儲(chǔ)器。由于CPU的速度遠(yuǎn)高于主內(nèi)存，CPU直接從內(nèi)存中存取數(shù)據(jù)要等待一定時(shí)間周期，Cache中保存著CPU剛用過(guò)或循環(huán)使用的一部分?jǐn)?shù)據(jù)，當(dāng)CPU再次使用該部分?jǐn)?shù)據(jù)時(shí)可從Cache中直接調(diào)用，這樣就減少了CPU的等待時(shí)間，提高了系統(tǒng)的效率。Cache又分為一級(jí)Cache(L1Cache)和二級(jí)Cache(L2Cache)，L1Cache集成在CPU內(nèi)部，L2Cache一般是焊在主板上，常見(jiàn)主板上焊有256KB或512KBL2Cache。

3、ROM：ROM(只讀存儲(chǔ)器)是一種存儲(chǔ)計(jì)算機(jī)指令和數(shù)據(jù)的半導(dǎo)體芯片，但只能從其中讀出數(shù)據(jù)而不能寫(xiě)入數(shù)據(jù)，關(guān)機(jī)或斷電后ROM的數(shù)據(jù)不會(huì)丟失。生產(chǎn)廠(chǎng)商把一些重要的不允許用戶(hù)更改的信息和程序存放在ROM中，例如存放在主板和顯示卡ROM中的BIOS程序。各存儲(chǔ)器速度比較綜上所述速度從快到慢次序?yàn)椋杭拇嫫鳎癈PU主頻相同）高速緩存（CACHE，內(nèi)存的一種）內(nèi)存（RAM和ROM）硬盤(pán)光盤(pán)軟盤(pán)例：CPU訪(fǎng)問(wèn)內(nèi)存的速度比訪(fǎng)問(wèn)下列哪個(gè)存儲(chǔ)設(shè)備要慢（）A）寄存器B）硬盤(pán)C）軟盤(pán)D）磁帶E）光盤(pán)（第九屆初賽試題）數(shù)制轉(zhuǎn)換由于計(jì)算機(jī)內(nèi)采用的是二進(jìn)制而實(shí)際生活中采用十進(jìn)制所以數(shù)制轉(zhuǎn)換是常見(jiàn)的題目十進(jìn)制Decimalsystem(逢十進(jìn)一)

碼：0，1，2，3，4，5，6，7，8，9

基：10

權(quán)：表達(dá)式：

二進(jìn)制Binarysystem(逢二進(jìn)一)

碼：0，1

基：2權(quán)：

表達(dá)式：

十六進(jìn)制Hexadecimal

碼：0，1，2，3，4，5，6，7，8，9，A,B,C,D,E,F

基：16權(quán)：表達(dá)式：

N進(jìn)制

碼：0，1，2，3，4，5，6，------，（N-1）

基：N

權(quán)：表達(dá)式：通常用數(shù)字右下角的角標(biāo)來(lái)表示數(shù)制，以防混淆運(yùn)算規(guī)則：滿(mǎn)k進(jìn)一，借一當(dāng)k設(shè)數(shù)字N的k進(jìn)制表示形式為則N的具體數(shù)值（含義）為數(shù)制不同，表達(dá)形式不同，但含義不變，如基數(shù)越大，表示形式越精練，但符號(hào)種類(lèi)也越多數(shù)制轉(zhuǎn)換非十進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)十進(jìn)制數(shù)轉(zhuǎn)換為非十進(jìn)制數(shù)非十進(jìn)制數(shù)之間的轉(zhuǎn)換非十進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)方法：多項(xiàng)式展開(kāi)r進(jìn)制的數(shù)，轉(zhuǎn)換為十進(jìn)制數(shù)：例如：數(shù)制轉(zhuǎn)換（1）十進(jìn)制數(shù)轉(zhuǎn)換為非十進(jìn)制數(shù)整數(shù)部分：除基取余，逆取例如：(53)10轉(zhuǎn)換為二進(jìn)制的過(guò)程如下：數(shù)制轉(zhuǎn)換（2）十進(jìn)制數(shù)轉(zhuǎn)換為非十進(jìn)制數(shù)小數(shù)部分：乘基取整，順取例如：(0.6875)10轉(zhuǎn)換為二進(jìn)制的過(guò)程如下，二進(jìn)制表示形式為0.1011數(shù)制轉(zhuǎn)換（3）非十進(jìn)制數(shù)之間的轉(zhuǎn)換一般方法：先將r進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)，再將十進(jìn)制數(shù)轉(zhuǎn)換為k進(jìn)制數(shù)特殊情況二－八進(jìn)制二-十六進(jìn)制數(shù)制轉(zhuǎn)換（4）例題計(jì)算機(jī)內(nèi)數(shù)的表示原碼，反碼，補(bǔ)碼一字節(jié)數(shù)據(jù)可表示的范圍是0--255，那么負(fù)數(shù)又怎么表示呢？原來(lái)在計(jì)算機(jī)中是這樣規(guī)定的，用一個(gè)數(shù)的最高一位表示正負(fù)，0為正，1為負(fù).如0111,1111轉(zhuǎn)換為十進(jìn)制為127，1111,1111為-127，由此我們知一字節(jié)的范圍為-127--127，其他字節(jié)的范圍類(lèi)推.

上面講的都是原碼表示法，可在計(jì)算機(jī)中的數(shù)據(jù)都是以補(bǔ)碼存放的，只有這樣才能減輕cpu的負(fù)擔(dān).提到補(bǔ)碼，就不得不提反碼了.計(jì)算機(jī)中是這樣規(guī)定反碼的，如果是正數(shù)，則按原碼形式不變，如127仍為0111,1111；而如果為負(fù)數(shù)則，第一位為1，其他各位取反（即0變?yōu)?，1變?yōu)?），如原碼-127（1111,1111），表示為1000,0000.補(bǔ)碼同上，如果是正數(shù)，則按原碼形式不變，如127仍為0111,1111；如果為負(fù)數(shù)則除第一位為1外，其他各位取反加1，如-127，先取反為1000,0000，然后加1，為1000,0001.但1000,0000比較特殊，用它來(lái)表示-128，由此我們知補(bǔ)碼可表示的范圍是-128--127。大家必須熟練掌握這三種碼之間的相互轉(zhuǎn)換如已知補(bǔ)碼寫(xiě)出反碼等。原碼，反碼，補(bǔ)碼舉例1、[X]補(bǔ)碼=10011000，其原碼為（）。011001111111010001110011001100101第七屆NOIP提高組初賽試題（符號(hào)不變，其余各位取反加1）2、已知x=（0.1011010）2，則[X/2]補(bǔ)=（）20.1011101111101100.01011010.100110第八屆NOIP提高組試題分析：這是一個(gè)正小數(shù)，可以把第一0看成是符號(hào)位，除以2相當(dāng)于整個(gè)右移，即為0.0101101而正數(shù)補(bǔ)碼及原碼相同所以正確答案為C計(jì)算機(jī)內(nèi)的編碼ASCII碼(美國(guó)標(biāo)準(zhǔn)信息交換碼)ASCII碼就是字符在計(jì)算機(jī)內(nèi)的編碼。如果計(jì)算機(jī)采用的編碼方式是ASCII的話(huà)，一個(gè)字符在計(jì)算機(jī)內(nèi)實(shí)際上就是以它的ASCII碼值儲(chǔ)存的。

例如，'A'的ASCII碼是65。那么，計(jì)算機(jī)存了一個(gè)字符'A'，實(shí)際上是存了一個(gè)數(shù)字65。在計(jì)算機(jī)內(nèi)兩者沒(méi)區(qū)別，'A'就是65，65就是'A'，漢字及全角英、數(shù)字符編碼漢字在計(jì)算機(jī)內(nèi)的編碼通常用輸入碼（外碼）、機(jī)內(nèi)碼、字模碼描述。機(jī)內(nèi)碼中用于漢字的存儲(chǔ)、處理交換等操作的計(jì)算機(jī)內(nèi)部代碼。一個(gè)漢字機(jī)內(nèi)碼通常用兩個(gè)字節(jié)表示，且這兩個(gè)字節(jié)的最高位均為1，以區(qū)別英文字符的ASCII碼；輸入碼是用來(lái)輸入漢字的編碼。拼音、字形碼、五筆字型、區(qū)位碼等字模碼是漢字的輸出編碼，計(jì)算機(jī)內(nèi)的字庫(kù)中存放的就是字模碼；機(jī)內(nèi)碼及漢字字符是一一對(duì)應(yīng)機(jī)內(nèi)碼及輸入碼是一對(duì)多關(guān)系，表明一個(gè)漢字的輸入方法有多種；機(jī)內(nèi)碼及字模碼也是一對(duì)多，表明一個(gè)漢字的輸出形式有多種，即有不同的字體輸出。(A)國(guó)標(biāo)碼國(guó)標(biāo)標(biāo)中所有符號(hào)按區(qū)位編排：94*941~15區(qū)：西文字母、數(shù)字、圖形符號(hào)，用戶(hù)自定義的專(zhuān)用符號(hào)，如10~15空，由用戶(hù)自定義。16區(qū)~55區(qū)：一級(jí)漢字，按拼音排序；

56區(qū)~87區(qū)：二級(jí)漢字，接部首排序，國(guó)標(biāo)碼用兩個(gè)字節(jié)的十六進(jìn)制表示，如國(guó)際碼“啊”，3021H（B）漢字機(jī)內(nèi)碼以GB2312－80標(biāo)準(zhǔn)為基礎(chǔ)，長(zhǎng)度兩個(gè)字節(jié)編碼每個(gè)字節(jié)的低七位表示漢字信息，把最高位變成1，即成漢字內(nèi)碼例：“啊”國(guó)標(biāo)碼是3021H，其機(jī)內(nèi)碼B0A1H（十六進(jìn)制表示）第1字節(jié)第2字節(jié)

0011000000100001高位置1

1011

0000

1010

0001B0A1特點(diǎn)：能及ASCII嚴(yán)格區(qū)分，ASCII碼<7F,機(jī)內(nèi)碼>7F代碼字長(zhǎng)短及國(guó)標(biāo)碼有簡(jiǎn)單一一對(duì)應(yīng)關(guān)系(C)機(jī)外碼區(qū)位碼：由漢字或字符的區(qū)號(hào)和位號(hào)所組成，用十進(jìn)制表示；（第1字節(jié)為區(qū)號(hào)，第2字節(jié)為位號(hào)）無(wú)重碼不好記代碼短及國(guó)標(biāo)碼有簡(jiǎn)單的對(duì)應(yīng)關(guān)系區(qū)位碼及國(guó)標(biāo)碼、機(jī)內(nèi)碼關(guān)系：區(qū)位號(hào)（十六進(jìn)制表示）+20H國(guó)標(biāo)碼（因?yàn)閲?guó)標(biāo)碼從21H開(kāi)始編）國(guó)標(biāo)碼+80H機(jī)內(nèi)碼，所以機(jī)內(nèi)碼總大于A1H例：“愛(ài)”的區(qū)位碼為1614，國(guó)標(biāo)碼、機(jī)內(nèi)碼？1614的十六進(jìn)制=100E分別+2020H=302E（國(guó)標(biāo)碼）302E+8080H=B0AE（機(jī)內(nèi)碼）求：4687區(qū)位碼對(duì)應(yīng)機(jī)內(nèi)碼CEF7國(guó)標(biāo)碼：也可作漢字輸入，特點(diǎn)同上首尾碼：按漢字形狀編碼。代碼短，兩鍵；重碼多；不易記拼音碼不需記憶；重碼多，代碼有時(shí)長(zhǎng)五筆字型碼易記，重碼少漢字鍵盤(pán)一鍵一字；鍵盤(pán)大聯(lián)機(jī)手寫(xiě)輸入不用學(xué)、不用記、操作方便，但識(shí)別困難、成本高語(yǔ)音輸入進(jìn)行語(yǔ)音識(shí)別，A/D轉(zhuǎn)換(C)機(jī)外碼(D)漢字編碼及漢字點(diǎn)陣字模漢字點(diǎn)陣字模：用二進(jìn)制的1或0所表示出的漢字的點(diǎn)陣模型。有：簡(jiǎn)易型16×16；普及型24×24提高型32×32；精密型48×48漢字庫(kù):存儲(chǔ)漢字點(diǎn)陣字模的存儲(chǔ)器存在磁盤(pán)的漢字庫(kù)——軟字庫(kù)，用時(shí)調(diào)入內(nèi)存存在ROM的漢字庫(kù)——硬字庫(kù)（漢卡），不占內(nèi)存漢字點(diǎn)陣存儲(chǔ)方式一般為16點(diǎn)陣、24點(diǎn)陣漢字庫(kù)中尋找漢字字模時(shí)采用地址碼漢字處理過(guò)程輸入碼機(jī)內(nèi)碼地址碼字形碼。全角的英、數(shù)字符相當(dāng)于一個(gè)漢字，半角的一個(gè)英、數(shù)字符及全角的它們碼長(zhǎng)度不同，并且二碼間無(wú)關(guān)系實(shí)例1、2KB的內(nèi)存能存儲(chǔ)（A）個(gè)漢字的機(jī)內(nèi)碼10245162048218定點(diǎn)數(shù)和浮點(diǎn)數(shù)1、定點(diǎn)數(shù)：在計(jì)算機(jī)中一個(gè)數(shù)的小數(shù)點(diǎn)的位置是固定的

（1）純小數(shù)表示法

符號(hào)位

.數(shù)值部分

（2）整數(shù)表示法

符號(hào)位

數(shù)值部分.

2、浮點(diǎn)數(shù)：在計(jì)算機(jī)中一個(gè)數(shù)的小數(shù)點(diǎn)的位置是浮動(dòng)的。一個(gè)浮點(diǎn)數(shù)的表示分為階碼和尾數(shù)兩個(gè)部分：

N＝M×2e

其中e是一個(gè)二進(jìn)制整數(shù)，M是二進(jìn)制小數(shù)，這里稱(chēng)e為數(shù)N的階碼，M稱(chēng)為數(shù)N的尾數(shù)，M表示了數(shù)N的全部有效數(shù)字，階碼e指明了小數(shù)點(diǎn)的位置。定點(diǎn)數(shù)和浮點(diǎn)數(shù)計(jì)算機(jī)系統(tǒng)的發(fā)展過(guò)程中，曾經(jīng)提出過(guò)多種方法表達(dá)實(shí)數(shù)。典型的比如相對(duì)于浮點(diǎn)數(shù)的定點(diǎn)數(shù)（FixedPointNumber）。在這種表達(dá)方式中，小數(shù)點(diǎn)固定的位于實(shí)數(shù)所有數(shù)字中間的某個(gè)位置。貨幣的表達(dá)就可以使用這種方式，比如99.00或者00.99可以用于表達(dá)具有四位精度（Precision），小數(shù)點(diǎn)后有兩位的貨幣值。由于小數(shù)點(diǎn)位置固定，所以可以直接用四位數(shù)值來(lái)表達(dá)相應(yīng)的數(shù)值。SQL中的NUMBER數(shù)據(jù)類(lèi)型就是利用定點(diǎn)數(shù)來(lái)定義的。還有一種提議的表達(dá)方式為有理數(shù)表達(dá)方式，即用兩個(gè)整數(shù)的比值來(lái)表達(dá)實(shí)數(shù)。定點(diǎn)數(shù)表達(dá)法的缺點(diǎn)在于其形式過(guò)于僵硬，固定的小數(shù)點(diǎn)位置決定了固定位數(shù)的整數(shù)部分和小數(shù)部分，不利于同時(shí)表達(dá)特別大的數(shù)或者特別小的數(shù)。最終，絕大多數(shù)現(xiàn)代的計(jì)算機(jī)系統(tǒng)采納了所謂的浮點(diǎn)數(shù)表達(dá)方式。這種表達(dá)方式利用科學(xué)計(jì)數(shù)法來(lái)表達(dá)實(shí)數(shù)，即用一個(gè)尾數(shù)（Mantissa），一個(gè)基數(shù)（Base），一個(gè)指數(shù)（Exponent）以及一個(gè)表示正負(fù)的符號(hào)來(lái)表達(dá)實(shí)數(shù)。比如123.45用十進(jìn)制科學(xué)計(jì)數(shù)法可以表達(dá)為1.2345×102，其中1.2345為尾數(shù)，10為基數(shù)，2為指數(shù)。浮點(diǎn)數(shù)利用指數(shù)達(dá)到了浮動(dòng)小數(shù)點(diǎn)的效果，從而可以靈活地表達(dá)更大范圍的實(shí)數(shù)。提示:尾數(shù)有時(shí)也稱(chēng)為有效數(shù)字（Significand）。尾數(shù)實(shí)際上是有效數(shù)字的非正式說(shuō)法。在IEEE標(biāo)準(zhǔn)中，浮點(diǎn)數(shù)是將特定長(zhǎng)度的連續(xù)字節(jié)的所有二進(jìn)制位分割為特定寬度的符號(hào)域，指數(shù)域和尾數(shù)域三個(gè)域，其中保存的值分別用于表示給定二進(jìn)制浮點(diǎn)數(shù)中的符號(hào)，指數(shù)和尾數(shù)。這樣，通過(guò)尾數(shù)和可以調(diào)節(jié)的指數(shù)（所以稱(chēng)為"浮點(diǎn)"）就可以表達(dá)給定的數(shù)值了。具體的格式參見(jiàn)下面的圖例：在上面的圖例中，第一個(gè)域?yàn)榉?hào)域。其中0表示數(shù)值為正數(shù)，而1則表示負(fù)數(shù)。第二個(gè)域?yàn)橹笖?shù)域，對(duì)應(yīng)于我們之前介紹的二進(jìn)制科學(xué)計(jì)數(shù)法中的指數(shù)部分。其中單精度數(shù)為8位，雙精度數(shù)為11位。以單精度數(shù)為例，8位的指數(shù)為可以表達(dá)0到255之間的255個(gè)指數(shù)值。但是，指數(shù)可以為正數(shù)，也可以為負(fù)數(shù)。為了處理負(fù)指數(shù)的情況，實(shí)際的指數(shù)值按要求需要加上一個(gè)偏差（Bias）值作為保存在指數(shù)域中的值，單精度數(shù)的偏差值為127，而雙精度數(shù)的偏差值為1023。比如，單精度的實(shí)際指數(shù)值0在指數(shù)域中將保存為127；而保存在指數(shù)域中的64則表示實(shí)際的指數(shù)值-63。偏差