初等演算法信息學

❶ 關於初中的NOIP問題

這是我從
中華信息學競賽網http://www.100xinxi.com/上
復制過來的NOIP大綱,你自己看看吧,還什麼不懂的,你直接去那看吧``(中華信息學競賽網)
由中國計算機學會負責組織的全國青少年信息學奧林匹克聯賽（National Olympiad in Informatics in Provinces, 簡稱NOIP）是全國信息學奧林匹克競賽（NOI）系列活動中的一個重要組成部分，旨在向中學生普及計算機基礎知識，培養計算機科學和工程領域的後備人才。普及的重點是根據中學生的特點，培養學生學習計算機的興趣，使得他們對信息技術的一些核心內容有更多的了解，提高他們創造性地運用程序設計知識解決實際問題的能力。對學生的能力培養將注重以下的幾個方面：
1.想像力與創造力；
2.對問題的理解和分析能力；
3.數學能力和邏輯思維能力；
4.對客觀問題和主觀思維的口頭和書面表達能力；
5.人文精神：包括與人的溝通能力，團隊精神與合作能力，恆心和毅力，審美能力等。
二、命題程序和組織機構
命題是考核和選拔過程中的重要一環，對計算機的普及的內容具有導向性作用。命題應注重趣味性、新穎性、知識性、應用性和中學生的心智特點，不直接從大學專業教材中選題。
在命題和審題工作中，堅持開放和規范的原則。在NOI科學委員會主持下成立的NOIP命題委員會負責命題工作，命題委員會成員主要來自參加NOIP的省（ 包括直轄市、自治區，下同。每個省最多派一名委員），也可來自社會計算機界。NOIP命題委員會的主要職責是提供NOIP的備選題目，並承擔對所提供的題目保密的責任。
1. NOIP命題委員會委員應具備如下資格：
從事一線計算機教學或信息學奧賽輔導工作兩年（含）以上；
有精力和時間從事該項工作；
對此項工作有興趣並願意作為志願者從事NOIP命題及其相關工作。
2. NOIP命題委員會委員的產生過程：
本人提出申請（填寫表格）；
中學教師需得到所在單位同意或省奧賽主管部門同意；
科學委員會批准，由中國計算機學會頒發聘書（每一聘期為兩年）。
3. NOIP命題委員會委員的職責：
每年為NOIP提供備選題題目若干，在9月1日之前提交科學委員會；
備選試題的保密期為2年，在該段時間內不得泄密或另作他用；
搜集本省信息學奧賽的有關信息並向科學委員會通報；
4. 題目一經提交，即表明同意授權中國計算機學會科學委員會全權處理，包括使用、修改和出版。試題原型被科學委員會採用後，中國計算機學會將為命題者頒發試題錄用證書，並頒發酬金。無論是委員提交的題目還是科學委員會直接提交的題目，試題版權均歸中國計算機學會所有。NOIP所用試題由科學委員會確定，這些試題可能從備選題庫中選取並做適當修改後成型，也可能直接命題。
三、競賽形式和成績評定
NOIP分兩個等級組：普及組和提高組。每組競賽分兩輪：初試和復試。
初試形式為筆試，側重考察學生的計算機基礎知識和編程的基本能力，並對知識面的廣度進行測試。初試為資格測試，獲本省初試成績在本賽區前
15%的學生進入復賽。
復試形式為上機編程，著重考察學生對問題的分析理解能力，數學抽象能力，編程語言的能力和編程技巧、想像力和創造性等。各省NOIP的等第獎在復試的優勝者中產生。
比賽中使用的程序設計語言是：
初賽：PASCAL或C/C++：
復賽：PASCAL或C/C++。
每年復賽結束後，各省必須在指定時間內將本省一等獎候選人的有關情況、源程序和可執行程序報送科學委員會。經復審和評測後，由中國計算機學會報送中國科協和教育部備案。中國計算機學會對各省獲NOIP二等獎和三等獎的分數線或比例提出指導性意見，各省可按照成績確定獲獎名單。
四、試題形式
每次NOIP的試題分四組：普及組初賽題A1、普及組復賽題A2、提高組初賽題B1和提高組復賽題B2。其中，A1和B1類型基本相同，A2和B2類型基本相同，但題目不完全相同，提高組難度高於普及組。
（一）初賽
初賽全部為筆試，滿分100分。試題由四部分組成：
1、選擇題：共20題，每題1.5分，共計30分。每題有5個備選答案，前10個題為單選題（即每題有且只有一個正確答案，選對得分），後10題為不定項選擇題（即每題有1至5個正確答案，只有全部選對才得分）。普及組20個都是單選題。
2、問題求解題：共2題，每題5分，共計10分。試題給出一個敘述較為簡單的問題，要求學生對問題進行分析，找到一個合適的演算法，並推算出問題的解。考生給出的答案與標准答案相同，則得分；否則不得分。
3、程序閱讀理解題：共4題，每題8分，共計32分。題目給出一段程序（不一定有關於程序功能的說明），考生通過閱讀理解該段程序給出程序的輸出。輸出與標准答案一致，則得分；否則不得分。
4、程序完善題：共2題，每題14分，共計28分。題目給出一段關於程序功能的文字說明，然後給出一段程序代碼，在代碼中略去了若干個語句或語句的一部分並在這些位置給出空格，要求考生根據程序的功能說明和代碼的上下文，填出被略去的語句。填對則得分；否則不得分。
（二）復賽
復賽的題型和考試形式與NOI類似，全部為上機編程題，但難度比NOI低。題目包括4道題，每題100分，共計400分。每一試題包括：題目、問題描述、輸入輸出要求、樣例描述及相關說明。測試時，測試程序為每道題提供了5-10組測試數據，考生程序每答對一組得10－20分，累計分即為該道題的得分。
五、試題的知識范圍
（一）初賽內容與要求：

計基
算本
機常
的識 1．計算機和信息社會（信息社會的主要特徵、計算機的主要特徵、數字通信網路的主要特徵、數字化）
2．信息輸入輸出基本原理（信息交換環境、文字圖形多媒體信息的輸入輸出方式）
3．信息的表示與處理（信息編碼、微處理部件MPU、內存儲結構、指令，程序，和存儲程序原理、程序的三種基本控制結構）
4．信息的存儲、組織與管理（存儲介質、存儲器結構、文件管理、資料庫管理）
5．信息系統組成及互連網的基本知識（計算機構成原理、槽和埠的部件間可擴展互連方式、層次式的互連結構、互聯網路、TCP/IP協議、HTTP協議、WEB應用的主要方式和特點）
6．人機交互界面的基本概念（窗口系統、人和計算機交流信息的途徑（文本及交互操作））
7．信息技術的新發展、新特點、新應用等。

計基
算本
機操
的作 1. Windows和LINUX的基本操作知識
2. 互聯網的基本使用常識 （網上瀏覽、搜索和查詢等）
3. 常用的工具軟體使用（文字編輯、電子郵件收發等）

程
序
設
計
的
基
本
知
識
數
據
結
構 1．程序語言中基本數據類型(字元、整數、長整、浮點)
2. 浮點運算中的精度和數值比較
3．一維數組（串）與線性表
4．記錄類型（PASCAL）/ 結構類型（C）
程
序
設
計 1．結構化程序設計的基本概念
2．閱讀理解程序的基本能力
3．具有將簡單問題抽象成適合計算機解決的模型的基本能力
4．具有針對模型設計簡單演算法的基本能力
5．程序流程描述（自然語言/偽碼/NS圖/其他）
6．程序設計語言（PASCAL/C/C++）- 2003仍允許BASIC
基本
演算法
處 理 1．初等演算法（計數、統計、數學運算等）
2．排序演算法（冒泡法、插入排序、合並排序、快速排序）
3．查找（順序查找、二分法）
4．回溯演算法

（二）復賽內容與要求：
在初賽內容的基礎上增加以下內容：
數
據
結
構 1．指針類型
2．多維數組
3．單鏈表及循環鏈表
4．二叉樹
5．文件操作（從文本文件中讀入數據，並輸出到文本文件中）
程
序
設
計 1．演算法的實現能力
2．程序調試基本能力
3．設計測試數據的基本能力
4．程序的時間復雜度和空間復雜度的估計
算
法
處
理 1．離散數學知識的應用（如排列組合、簡單圖論、數理邏輯）
2．分治思想
3．模擬法
4．貪心法
5．簡單搜索演算法（深度優先 廣度優先）搜索中的剪枝
6．動態規劃的思想及基本演算法

六、試題保密紀律
關於保密以及考試的紀律見NOI條例。NOIP主辦單位中國計算機學會負責NOIP的紀律監察工作並接受投訴，加強過程監管，防止賽題泄漏、考場舞弊、弄虛作假等現象的發生。一旦查實命題委員會委員泄密備選試題，考場泄題或舞弊，或篡改試卷和考試成績者，主辦單位將根據NOI條例及其有關規則予以懲罰。

❷ c語言（高分）

1.相對於遞歸演算法,遞推演算法免除了數據進出棧的過程，也就是說,不需要函數不斷的向邊界值靠攏,而直接從邊界出發,直到求出函數值.
比如階乘函數：f(n)=n*f(n-1)
在f(3)的運算過程中,遞歸的數據流動過程如下:
f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}
而遞推如下:
f(0)-->f(1)-->f(2)-->f(3)
由此可見,遞推的效率要高一些,在可能的情況下應盡量使用遞推.但是遞歸作為比較基礎的演算法,它的作用不能忽視.所以,在把握這兩種演算法的時候應該特別注意.
2.所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
分類
在計算機科學所使用的排序演算法通常被分類為：
計算的復雜度（最差、平均、和最好表現），依據串列（list）的大小（n）。一般而言，好的表現是O。(n log n)，且壞的行為是Ω(n2)。對於一個排序理想的表現是O(n)。僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要Ω(n log n)。
記憶體使用量（以及其他電腦資源的使用）
穩定度：穩定排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。也就是一個排序演算法是穩定的，就是當有兩個有相等關鍵的紀錄R和S，且在原本的串列中R出現在S之前，在排序過的串列中R也將會是在S之前。
一般的方法：插入、交換、選擇、合並等等。交換排序包含冒泡排序（bubble sort）和快速排序（quicksort）。選擇排序包含shaker排序和堆排序（heapsort）。
當相等的元素是無法分辨的，比如像是整數，穩定度並不是一個問題。然而，假設以下的數對將要以他們的第一個數字來排序。
(4, 1) (3, 1) (3, 7) (5, 6)
在這個狀況下，有可能產生兩種不同的結果，一個是依照相等的鍵值維持相對的次序，而另外一個則沒有：
(3, 1) (3, 7) (4, 1) (5, 6) (維持次序)
(3, 7) (3, 1) (4, 1) (5, 6) (次序被改變)
不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地時作為穩定。作這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個物件間之比較，就會被決定使用在原先資料次序中的條目，當作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負擔。
排列演算法列表
在這個表格中，n是要被排序的紀錄數量以及k是不同鍵值的數量。
穩定的
冒泡排序（bubble sort） — O(n2)
雞尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n2)
插入排序 （insertion sort）— O(n2)
桶排序 （bucket sort）— O(n); 需要 O(k) 額外 記憶體
計數排序 (counting sort) — O(n+k); 需要 O(n+k) 額外 記憶體
歸並排序 （merge sort）— O(n log n); 需要 O(n) 額外記憶體
原地歸並排序 — O(n2)
二叉樹排序 （Binary tree sort） — O(n log n); 需要 O(n) 額外記憶體
鴿巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外記憶體
基數排序 （radix sort）— O(n·k); 需要 O(n) 額外記憶體
Gnome sort — O(n2)
Library sort — O(n log n) with high probability, 需要 (1+ε)n 額外記憶體
不穩定
選擇排序 （selection sort）— O(n2)
希爾排序 （shell sort）— O(n log n) 如果使用最佳的現在版本
Comb sort — O(n log n)
堆排序 （heapsort）— O(n log n)
Smoothsort — O(n log n)
快速排序 （quicksort）— O(n log n) 期望時間, O(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最外情況時間, 需要 額外的 O(n + k) 空間, 也需要找到最長的遞增子序列（longest increasing subsequence）
不實用的排序演算法
Bogo排序 — O(n × n!) 期望時間, 無窮的最壞情況。
Stupid sort — O(n3); 遞回版本需要 O(n2) 額外記憶體
Bead sort — O(n) or O(√n), 但需要特別的硬體
Pancake sorting — O(n), 但需要特別的硬體
排序的演算法
排序的演算法有很多，對空間的要求及其時間效率也不盡相同。下面列出了一些常見的排序演算法。這裡面插入排序和冒泡排序又被稱作簡單排序，他們對空間的要求不高，但是時間效率卻不穩定；而後面三種排序相對於簡單排序對空間的要求稍高一點，但時間效率卻能穩定在很高的水平。基數排序是針對關鍵字在一個較小范圍內的排序演算法。
插入排序
冒泡排序
選擇排序
快速排序
堆排序
歸並排序
基數排序
希爾排序
插入排序
插入排序是這樣實現的：
首先新建一個空列表，用於保存已排序的有序數列（我們稱之為"有序列表"）。
從原數列中取出一個數，將其插入"有序列表"中，使其仍舊保持有序狀態。
重復2號步驟，直至原數列為空。
插入排序的平均時間復雜度為平方級的，效率不高，但是容易實現。它藉助了"逐步擴大成果"的思想，使有序列表的長度逐漸增加，直至其長度等於原列表的長度。
冒泡排序
冒泡排序是這樣實現的：
首先將所有待排序的數字放入工作列表中。
從列表的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。
重復2號步驟，直至再也不能交換。
冒泡排序的平均時間復雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。
選擇排序
選擇排序是這樣實現的：
設數組內存放了n個待排數字，數組下標從1開始，到n結束。
i=1
從數組的第i個元素開始到第n個元素，尋找最小的元素。
將上一步找到的最小元素和第i位元素交換。
如果i=n－1演算法結束，否則回到第3步
選擇排序的平均時間復雜度也是O(n²)的。
快速排序
現在開始，我們要接觸高效排序演算法了。實踐證明，快速排序是所有排序演算法中最高效的一種。它採用了分治的思想：先保證列表的前半部分都小於後半部分，然後分別對前半部分和後半部分排序，這樣整個列表就有序了。這是一種先進的思想，也是它高效的原因。因為在排序演算法中，演算法的高效與否與列表中數字間的比較次數有直接的關系，而"保證列表的前半部分都小於後半部分"就使得前半部分的任何一個數從此以後都不再跟後半部分的數進行比較了，大大減少了數字間不必要的比較。但查找數據得另當別論了。
堆排序
堆排序與前面的演算法都不同，它是這樣的：
首先新建一個空列表，作用與插入排序中的"有序列表"相同。
找到數列中最大的數字，將其加在"有序列表"的末尾，並將其從原數列中刪除。
重復2號步驟，直至原數列為空。
堆排序的平均時間復雜度為nlogn,效率高（因為有堆這種數據結構以及它奇妙的特徵，使得"找到數列中最大的數字"這樣的操作只需要O(1)的時間復雜度，維護需要logn的時間復雜度），但是實現相對復雜（可以說是這里7種演算法中比較難實現的）。
看起來似乎堆排序與插入排序有些相像，但他們其實是本質不同的演算法。至少，他們的時間復雜度差了一個數量級，一個是平方級的，一個是對數級的。
平均時間復雜度
插入排序 O(n2)
冒泡排序 O(n2)
選擇排序 O(n2)
快速排序 O(n log n)
堆排序 O(n log n)
歸並排序 O(n log n)
基數排序 O(n)
希爾排序 O(n1.25)
3.索引查找是在索引表和主表(即線性表的索引存儲結構)上進行的查找。索引查找的過程是：首先根據給定的索引值K1，在索引表上查找出索引值等於KI的索引項，以確定對應予表在主表中的開始位置和長度，然後再根據給定的關鍵字K2，茬對應的子表中查找出關鍵字等於K2的元素(結點)。對索引表或子表進行查找時，若表是順序存儲的有序表，則既可進行順序查找，也可進行二分查找，否則只能進行順序查找。
設數組A是具有mainlist類型的一個主表，數組B是具有inde)dist類型的在主表A 上建立的一個索引表，m為索引表B的實際長度，即所含的索引項的個數，KI和K2分別為給定待查找的索引值和關鍵字(當然它們的類型應分別為索引表中索引值域的類型和主表中關鍵字域在索引存儲中，不僅便於查找單個元素，而且更便於查找一個子表中的全部元素。當需要對一個子袁中的全部元素依次處理時，只要從索引表中查找出該子表的開始位
置即可。由此開始位置可以依次取出該子表中的每一個元素，所以整個查找過程的時間復雜度為，若不是採用索引存儲，而是採用順序存儲，即使把它組織成有序表而進行二分查找時，索引查找一個子表中的所有元素與二分查找一個子表中的所有元素相比。
若在主表中的每個子表後都預留有空閑位置，則索引存儲也便於進行插入和刪除運算，因為其運算過程只涉及到索引表和相應的子表，只需要對相應子表中的元素進行比較和移動，與其它任何子表無關，不像順序表那樣需涉及到整個表中的所有元素，即牽一發而動全身。
在線性表的索引存儲結構上進行插入和刪除運算的演算法，也同查找演算法類似，其過程為：首先根據待插入或刪除元素的某個域(假定子表就是按照此域的值劃分的)的值查找索引表，確定出對應的子表，然後再根據待插入或刪除元素的關鍵字，在該子表中做插入或刪除元素的操作。因為每個子表不是順序存儲，就是鏈接存儲，所以對它們做插入或刪除操作都是很簡單的。
4.插入法排序
#define N 10
#include"stdio.h"
main()
{ int i,j,k,t,a[N];
clrscr();
printf("Please input %d numbers:\n",N);
for(i=0;i<N;i++)
scanf("%d",&a[i]);
for(i=1;i<N;i++)
{
for(j=0;j<i;j++)
{if(a[j]>a[i])
{t=a[i];
for(k=i;k>=j;k--)
a[k]=a[k-1];
a[j]=t;
}
}
}
printf("small to big order:\n");
for(i=0;i<N;i++)
printf("%-2d",a[i]);
printf("\n");
getch();
}

❸ 參加ACM競賽需要用的參考書

ACM國際大學生程序設計競賽：知識與入門.pdf

鏈接: https://pan..com/s/19OY2FJUkk4RhW5WTsPkwfQ

《ACM國際大學生程序設計競賽:知識與入門》適用於參加ACM國際大學生程序設計競賽的本科生和研究生，對參加青少年信息學奧林匹克競賽的中學生也很有指導價值。