回溯法解決素?cái)?shù)環(huán)

算法分析實(shí)驗(yàn)報(bào)告回溯法-素?cái)?shù)環(huán)學(xué)生姓名：專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級：學(xué)號:指導(dǎo)教師：2023年6月12日目錄一、實(shí)驗(yàn)題目2二、實(shí)驗(yàn)?zāi)康?三、實(shí)驗(yàn)要求2四、實(shí)現(xiàn)過程31、實(shí)驗(yàn)設(shè)計(jì)：32、調(diào)試分析：73、運(yùn)行結(jié)果：84、實(shí)驗(yàn)總結(jié)：8五、參考文獻(xiàn)9一、實(shí)驗(yàn)題目回溯法-素?cái)?shù)環(huán)二、實(shí)驗(yàn)?zāi)康?．掌握回溯法的設(shè)計(jì)思想。2．了解和掌握各種經(jīng)典問題的回溯思想。三、實(shí)驗(yàn)要求1.[問題描述]：把整數(shù){1、2、3、····、20}填寫到一個(gè)環(huán)中，要求每個(gè)整數(shù)只能填寫一次，并且相鄰的兩個(gè)整數(shù)之和是一個(gè)素?cái)?shù)。2.[算法]：回溯法：在包含問題的所有可能解的解空間樹中，從根節(jié)點(diǎn)出發(fā)，按照深度優(yōu)先遍歷的策略進(jìn)行搜索，對于解空間樹種的某個(gè)節(jié)點(diǎn)，如果該節(jié)點(diǎn)滿足問題的約束條件，那么進(jìn)入該子樹繼續(xù)進(jìn)行搜索，否那么將以該節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹進(jìn)行剪枝?；厮莘ǔ３？梢苑乐顾械目赡芙猓?，適用于求解組合數(shù)中較大的問題?；厮莘◤慕饪臻g樹的根節(jié)點(diǎn)出發(fā)，按照深度優(yōu)先遍歷策略搜索滿足約束條件的解。在搜索至樹種某節(jié)點(diǎn)時(shí)，先判斷該節(jié)點(diǎn)對應(yīng)的局部是否滿足約束條件，也就是判斷該節(jié)點(diǎn)是否包含問題的〔最優(yōu)〕解，如果肯定不包含，那么跳過該節(jié)點(diǎn)為跟的子樹，即所謂剪枝；否那么，進(jìn)入以該節(jié)點(diǎn)為跟的子樹，繼續(xù)按照深度優(yōu)先遍歷策略進(jìn)行搜索。四、實(shí)現(xiàn)過程1、實(shí)驗(yàn)設(shè)計(jì)：1.這個(gè)素?cái)?shù)環(huán)有20個(gè)位置，每個(gè)位置可以填寫的整數(shù)位1~20，共20種可能，可以對每個(gè)位置從1開始進(jìn)行探索，約束條件是正在試探的數(shù)滿足如下約束條件：與已經(jīng)填寫的素?cái)?shù)環(huán)中的整數(shù)不重復(fù)；與前面相鄰的整數(shù)之和是一個(gè)素?cái)?shù)；最后一個(gè)填寫到素?cái)?shù)環(huán)中的整數(shù)與第一個(gè)填寫的整數(shù)之和是一個(gè)素?cái)?shù)。在填寫第K個(gè)位置時(shí)，如果滿足上述約束條件，那么繼續(xù)填寫第Ｋ＋１個(gè)位置；如果１～２０都無法填寫到第Ｋ個(gè)位置，那么取消對第Ｋ個(gè)位置的填寫，回溯到第Ｋ＋１個(gè)位置。2.圖解過程以下以{1、2、3、4}為例進(jìn)行圖解分析：由上圖可知有兩種結(jié)果：{1、2、3、4} {1、4、3、2}3.算法實(shí)現(xiàn)intPrime(intx)//判斷整數(shù)x是否素?cái)?shù){ inti,n; n=(int)sqrt(x); for(i=2;i<n;i++) if(x%i==0) return0; return1;}intcheck(intk){ intflag=0,n; for(inti=0;i<k;i++) { if(a[i]==a[k])//判斷是否重復(fù) return0; } flag=Prime(a[k]+a[k-1]); if(flag==1&&k==n-1)//判斷第一個(gè)和最后一個(gè)是否素?cái)?shù) flag=Prime(a[k]+a[0]); returnflag;}voidprimecircle(intn){ inti,k; for(i=0;i<n;i++) { a[i]=0;//將數(shù)組a[]初始化為0 } a[0]=1;k=1;//指定第0個(gè)位置填1 while(k>=1) { a[k]=a[k]+1; while(a[k]<=n) { if(check(k)==1)//位置k可以填寫數(shù)a[] break; else a[k]=a[k]+1;//試探下一個(gè)數(shù) } if(a[k]<=n&&k==n-1)//求解完畢輸出解 { for(i=0;i<n;i++) { cout<<a[i]<<""<<endl; } return; } if(a[k]<=n&&k<n-1)//填寫下一個(gè)位置 k=k+1; else a[k--]=0;//回溯 }2、調(diào)試分析：設(shè)要填寫1—n共n個(gè)整數(shù)，由于每個(gè)位置可以填寫的情況有n種，因此，素?cái)?shù)環(huán)問題的解空間數(shù)是一棵完全n叉樹，且樹的深度為n+1，因此，最壞情況下的時(shí)間性能為O〔n?〕。3、運(yùn)行結(jié)果：4、實(shí)驗(yàn)總結(jié)：通過本次實(shí)驗(yàn)加深了我對回溯算法所給的模式的理解，同時(shí)對用回溯算法解決一個(gè)實(shí)際問題有了一個(gè)更深層次的認(rèn)識?；厮菟惴ǚ沁f歸的模式通用，用它解決一個(gè)問題的關(guān)鍵是找出合法解與局部解的判斷條件，在合法解時(shí)書寫相應(yīng)程序段，在局部解時(shí)書寫相應(yīng)程序段。另外注意有些條件局部解和合法解都要滿足，此時(shí)要排除掉非法解，即要給它剪去。另外需要注意的是回溯的過程?？傊?，通過本次實(shí)驗(yàn)使我掌握了回溯算法非遞歸的一般模式，以后在解決一類問題時(shí)可以照著這個(gè)模式編寫程序。通過本次試驗(yàn)，自己根本上掌握上述算法原