



全文預(yù)覽已結(jié)束
下載本文檔
版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
關(guān)于符號(hào)三角形數(shù)與n的關(guān)系的研究與實(shí)現(xiàn)云南師范大學(xué) 計(jì)算機(jī)應(yīng)用技術(shù) 張書(shū)涵1 問(wèn)題描述在一般情況下,符號(hào)三角形的第一行有n個(gè)符號(hào)。符號(hào)三角形問(wèn)題要求對(duì)于給定的n,計(jì)算有多少個(gè)不同的符號(hào)三角形,使其所含的“+”和“-”的個(gè)數(shù)相同。例如圖1:由14個(gè)“+”和14個(gè)“-”組成的符號(hào)三角形。2個(gè)同號(hào)下面都是“+”,2個(gè)異號(hào)下面都是“-”。+ + - + - + + - - - - +- + + + - + + - + - -+ 圖1 符號(hào)三角形本文就是計(jì)算有多少個(gè)不同的符號(hào)三角形,使其所含的“+”和“-”的個(gè)數(shù)相同,并且探討兩種符號(hào)數(shù)相同的不同符號(hào)三角形的個(gè)數(shù)與n的關(guān)系。2 問(wèn)題分析用n元組x1:n表示符號(hào)三角形的第一行。Xi=1表示第一行第i個(gè)符號(hào)為“+”, Xi=0表示第一行第i個(gè)符號(hào)為“-”??尚行约s束函數(shù)為,當(dāng)前符號(hào)三角形所包含的“+”個(gè)數(shù)與“-”個(gè)數(shù)均不超過(guò)n*(n+1)/4 。容易看出,第1行n個(gè)符號(hào)的數(shù)值不同,將直接導(dǎo)致符號(hào)三角形的數(shù)值F(n)不同。顯然,符號(hào)三角形的個(gè)數(shù)F(n)是隨著n的變化而變化。那么,得知F(n)與n必然存在一種關(guān)系。其次,一個(gè)符號(hào)三角形有n(n+1)/2個(gè)符號(hào),顯然這個(gè)公式的分子n,n+1中必有一個(gè)為偶數(shù)。記G(n)為一個(gè)符號(hào)三角形所包含的符號(hào)數(shù),假定n為偶數(shù)。則上述的公式可改寫(xiě)成:。而且n/2必須再次為偶數(shù),不然就不滿(mǎn)足條件:符號(hào)三角形的符號(hào)數(shù)G(n)所含的“+”和“”的個(gè)數(shù)相同。所以,n必然是4的倍數(shù),即n=4k,其中k=1,2,3,。根據(jù)上面的論述,易知當(dāng)公式的分子n,n+1中有且只有一個(gè)為4的倍數(shù),此探討才有意義,并且研究的條件再次收縮。3 問(wèn)題解決 用窮舉法列出n和符號(hào)數(shù)以及符號(hào)三角形數(shù)F(n)的映射表,如表1所示。n符號(hào)總數(shù)符號(hào)三角形個(gè)數(shù)F(n)110230364410651506210728128364094501055011661711278410表1 n和符號(hào)數(shù)以及符號(hào)三角形數(shù)F(n)的映射表根據(jù)窮舉的結(jié)果我們也可以看出,當(dāng)n=4i或n=4i-1(i=1,2,3,4)時(shí)存在符號(hào)三角形,當(dāng)n=4i-2或4i-3時(shí)不存在符號(hào)三角數(shù)。4 運(yùn)行結(jié)果 5 總結(jié)通過(guò)上述的分析,基本上理解了回溯算法。當(dāng)n=4i或n=4i-1(i=1,2,3,4)時(shí)存在符號(hào)三角形,當(dāng)n=4i-2或4i-3時(shí)不存在符號(hào)三角數(shù)。但是運(yùn)用現(xiàn)有的技術(shù)很難得到F(n)關(guān)于n的精確表達(dá)式。所以,這個(gè)問(wèn)題還有待進(jìn)一步研究。附錄:程序代碼:#includeiostream using namespace std; typedef unsigned char uchar; char cc2=+,-; /便于輸出 int n, /第一行符號(hào)總數(shù) half, /全部符號(hào)總數(shù)一半 counter; /1計(jì)數(shù),即“-”號(hào)計(jì)數(shù) uchar *p; /符號(hào)存儲(chǔ)空間 long sum; /符合條件的三角形計(jì)數(shù) /t,第一行第t個(gè)符號(hào) void Backtrace(int t) int i, j; if( t n ) /符號(hào)填充完畢 sum+; /打印符號(hào) cout 第 sum 個(gè):n; for(i=1; i=n; +i) for(j=1; ji; +j) cout ; for(j=1; j=n-i+1; +j) cout cc pij ; cout n; else for(i=0; i2; +i) p1t = i; /第一行第t個(gè)符號(hào) counter += i; /“-”號(hào)統(tǒng)計(jì) for(j=2; j=2時(shí),可以運(yùn)算出下面行的某些符號(hào) pjt-j+1 = pj-1t-j+1pj-1t-j+2;/通過(guò)異或運(yùn)算下行符號(hào) counter += pjt-j+1; if( (counter = half) & ( t*(t+1)/2 - counter = half) ) /若符號(hào)統(tǒng)計(jì)未超過(guò)半數(shù),并且另一種符號(hào)也未超過(guò)半數(shù) Backtrace(t+1); /在第一行增加下一個(gè)符號(hào) /回溯,判斷另一種符號(hào)情況 for(j=2; j=t; +j) counter -= pjt-j+1; counter -= i; int main() cout n; counter = 0; sum = 0; half = n*(n+1)/2; int i=0; if( half%2 = 0 ) /總數(shù)須為偶數(shù),若為奇數(shù)則無(wú)解 half /= 2; p = new uchar *n+1; for(i=0; i=n; +i) pi = new ucharn+1; memset(pi, 0, sizeo
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025合同中的‘隱秘風(fēng)險(xiǎn)’
- 2025年稀有金屬及稀土金屬材料項(xiàng)目建議書(shū)
- 2025標(biāo)準(zhǔn)工業(yè)倉(cāng)庫(kù)租賃合同范本
- 2025中國(guó)某省份教育行業(yè)教師之總集體合同范本
- 2025合作連鎖加盟合同范本
- 2025年敏感元件及傳感器項(xiàng)目建議書(shū)
- 2025年泌尿系統(tǒng)感染用藥項(xiàng)目合作計(jì)劃書(shū)
- 2025年軟件開(kāi)發(fā)、評(píng)測(cè)平臺(tái)合作協(xié)議書(shū)
- 2025年農(nóng)林牧漁專(zhuān)用儀器儀表項(xiàng)目建議書(shū)
- 2025年模組檢測(cè)系統(tǒng)合作協(xié)議書(shū)
- 2023年廣東學(xué)位英語(yǔ)試題學(xué)位英語(yǔ)考試真題(含答案)
- 《旅行社經(jīng)營(yíng)管理》考試復(fù)習(xí)題庫(kù)及答案
- 北師大版三年級(jí)數(shù)學(xué)下冊(cè)競(jìng)賽卷
- 粵教版五年級(jí)下冊(cè)科學(xué)知識(shí)點(diǎn)
- 危大工程巡視檢查記錄表(深基坑)
- 《最好的未來(lái)》合唱曲譜
- GB∕T 36765-2018 汽車(chē)空調(diào)用1,1,1,2-四氟乙烷(氣霧罐型)
- 《覺(jué)醒年代》朗誦稿
- 小學(xué)教育專(zhuān)業(yè)畢業(yè)論文
- 麗聲北極星分級(jí)繪本第二級(jí)上Dinner for a Dragon 課件
- 水保工程驗(yàn)收檢驗(yàn)記錄表
評(píng)論
0/150
提交評(píng)論