100. 數(shù)字移動
在圖中的九個點上,空出中間的點,其余的點上任意填入數(shù)字1到8;1的位置固定不動,然后移動其余的數(shù)字,使1到8順時針從小到大排列.移動的規(guī)律是:只能將數(shù)字沿線移向空白的點.
請編程顯示數(shù)字移動過程。
*題目分析與算法設(shè)計
分析題目中的條件,要求利用中間的空白格將數(shù)字順時針方向排列,且排列過程中只能借空白的點來移動數(shù)字.問題的實質(zhì)就是將矩陣外面的8個格看成一個環(huán),8個數(shù)字在環(huán)內(nèi)進行排序,同于受題目要求的限制"只能將數(shù)字沿線移向空白的點",所以要利用中間的空格進行排序,這樣要求的排序算法與眾不同.
觀察中間的點,它是一個與其它8個點有連線的點,即它是中心點.中心點的活動的空間,它可以向8個方向移動,充分利用中心點這個特性是算法設(shè)計成功與否的關(guān)鍵.
在找到1所在的位置后,其余各個數(shù)字的正確位置就是固定的.我們可以按照下列算法從數(shù)字2開始,一個一個地來調(diào)整各個數(shù)字的位置.
*確定數(shù)字i應(yīng)處的位置;
*從數(shù)字i應(yīng)處的位置開始,向后查找數(shù)字i現(xiàn)在的位置;
*若數(shù)字i現(xiàn)在位置不正確,則將數(shù)字i從現(xiàn)在的位置(沿連線)移向中間的空格,而將原有位置空出;依次將現(xiàn)有空格前的所有元素向后移動;直到將i應(yīng)處的位置空出,把它移入再次空出中間的格.
從數(shù)字2開始使用以上過程,就可以完成全部數(shù)字的移動排序.
編程時要將矩陣的外邊八個格看成一個環(huán),且環(huán)的首元素是不定的,如果算法設(shè)計得不好,程序中就要花很多精力來處理環(huán)中元素的前后順序問題.將題目中的3X3矩陣用一個一維數(shù)組表示,中間的元素(第四號)剛好為空格,設(shè)計另一個指針數(shù)組,專門記錄指針外八個格構(gòu)成環(huán)時的連接關(guān)系.指針數(shù)組的每個元素依次記錄環(huán)中數(shù)字在原來數(shù)組中對應(yīng)的元素下標.這樣通過指針數(shù)組將原來矩陣中復(fù)雜的環(huán)型關(guān)系表示成了簡單的線性關(guān)系,從而大大地簡化了程序設(shè)計.
*程序與程序注釋
#include
int a[]={0,1,2,5,8,7,6,3}; /*指針數(shù)組.依次存入矩陣中構(gòu)成環(huán)的元素下標*/
int b[9]; /*表示3X3矩陣,b[4]為空格*/
int c[9]; /*確定1所在的位置后,對環(huán)進行調(diào)整的指針數(shù)組*/
int count=0; /*數(shù)字移動步數(shù)計數(shù)器*/
void main()
{
int i,j,k,t;
void print();
printf("Please enter original order of digits 1~8:");
for(i=0;i<8;i++)
scanf("%d",&b[a[i>);
/*順序輸入矩陣外邊的8個數(shù)字,矩陣元素的順序由指針數(shù)組的元素a[i]控制*/
printf("The sorting process is as felow:\n");
print();
for(t=-1,j=0;j<8&&t==-1;j++) /*確定數(shù)字1所在的位置*/
if(b[a[j>==1) t=j; /*t:記錄數(shù)字1所在的位置*/
for(j=0;j<8;j++) /*調(diào)整環(huán)的指針數(shù)組,將數(shù)字1所在的位置定為環(huán)的首*/
c[j]=a[(j+t)%8];
for(i=2;i<9;i++) /*從2開始依次調(diào)整數(shù)字的位置*/
/*i:正在處理的數(shù)字,i對應(yīng)在環(huán)中應(yīng)當?shù)恼_位置就是i-1*/
for(j=i-1;j<8;j++) /*從i應(yīng)處的正確位置開始順序查找*/
if(b[c[j>==i&&j!=i-1) /*若i不在正確的位置*/
{
b[4]=i; /*將i移到中心的空格中*/
b[c[j>=0;print(); /*空出i原來所在的位置,輸出*/
for(k=j;k!=i-1;k--) /*將空格以前到i的正確位置之間的數(shù)字依次向后移動一格*/
{
b[c[k>=b[c[k-1>; /*數(shù)字向后移動*/
b[c[k-1>=0;
print();
}
b[c[k>=i; /*將中間的數(shù)字i移入正確的位置*/
b[4]=0; /*空出中間的空格*/
print();
break;
}
else if(b[c[j>==i) break; /*數(shù)字i在正確的位置*/
}
void print(void) /*按格式要求輸出矩陣*/
{
int c;
for(c=0;c<9;c++)
if(c%3==2) printf("%2d ",b[c]);
else printf("%2d",b[c]);
printf("----%2d----\n",count++);
}
在圖中的九個點上,空出中間的點,其余的點上任意填入數(shù)字1到8;1的位置固定不動,然后移動其余的數(shù)字,使1到8順時針從小到大排列.移動的規(guī)律是:只能將數(shù)字沿線移向空白的點.
請編程顯示數(shù)字移動過程。
*題目分析與算法設(shè)計
分析題目中的條件,要求利用中間的空白格將數(shù)字順時針方向排列,且排列過程中只能借空白的點來移動數(shù)字.問題的實質(zhì)就是將矩陣外面的8個格看成一個環(huán),8個數(shù)字在環(huán)內(nèi)進行排序,同于受題目要求的限制"只能將數(shù)字沿線移向空白的點",所以要利用中間的空格進行排序,這樣要求的排序算法與眾不同.
觀察中間的點,它是一個與其它8個點有連線的點,即它是中心點.中心點的活動的空間,它可以向8個方向移動,充分利用中心點這個特性是算法設(shè)計成功與否的關(guān)鍵.
在找到1所在的位置后,其余各個數(shù)字的正確位置就是固定的.我們可以按照下列算法從數(shù)字2開始,一個一個地來調(diào)整各個數(shù)字的位置.
*確定數(shù)字i應(yīng)處的位置;
*從數(shù)字i應(yīng)處的位置開始,向后查找數(shù)字i現(xiàn)在的位置;
*若數(shù)字i現(xiàn)在位置不正確,則將數(shù)字i從現(xiàn)在的位置(沿連線)移向中間的空格,而將原有位置空出;依次將現(xiàn)有空格前的所有元素向后移動;直到將i應(yīng)處的位置空出,把它移入再次空出中間的格.
從數(shù)字2開始使用以上過程,就可以完成全部數(shù)字的移動排序.
編程時要將矩陣的外邊八個格看成一個環(huán),且環(huán)的首元素是不定的,如果算法設(shè)計得不好,程序中就要花很多精力來處理環(huán)中元素的前后順序問題.將題目中的3X3矩陣用一個一維數(shù)組表示,中間的元素(第四號)剛好為空格,設(shè)計另一個指針數(shù)組,專門記錄指針外八個格構(gòu)成環(huán)時的連接關(guān)系.指針數(shù)組的每個元素依次記錄環(huán)中數(shù)字在原來數(shù)組中對應(yīng)的元素下標.這樣通過指針數(shù)組將原來矩陣中復(fù)雜的環(huán)型關(guān)系表示成了簡單的線性關(guān)系,從而大大地簡化了程序設(shè)計.
*程序與程序注釋
#include
int a[]={0,1,2,5,8,7,6,3}; /*指針數(shù)組.依次存入矩陣中構(gòu)成環(huán)的元素下標*/
int b[9]; /*表示3X3矩陣,b[4]為空格*/
int c[9]; /*確定1所在的位置后,對環(huán)進行調(diào)整的指針數(shù)組*/
int count=0; /*數(shù)字移動步數(shù)計數(shù)器*/
void main()
{
int i,j,k,t;
void print();
printf("Please enter original order of digits 1~8:");
for(i=0;i<8;i++)
scanf("%d",&b[a[i>);
/*順序輸入矩陣外邊的8個數(shù)字,矩陣元素的順序由指針數(shù)組的元素a[i]控制*/
printf("The sorting process is as felow:\n");
print();
for(t=-1,j=0;j<8&&t==-1;j++) /*確定數(shù)字1所在的位置*/
if(b[a[j>==1) t=j; /*t:記錄數(shù)字1所在的位置*/
for(j=0;j<8;j++) /*調(diào)整環(huán)的指針數(shù)組,將數(shù)字1所在的位置定為環(huán)的首*/
c[j]=a[(j+t)%8];
for(i=2;i<9;i++) /*從2開始依次調(diào)整數(shù)字的位置*/
/*i:正在處理的數(shù)字,i對應(yīng)在環(huán)中應(yīng)當?shù)恼_位置就是i-1*/
for(j=i-1;j<8;j++) /*從i應(yīng)處的正確位置開始順序查找*/
if(b[c[j>==i&&j!=i-1) /*若i不在正確的位置*/
{
b[4]=i; /*將i移到中心的空格中*/
b[c[j>=0;print(); /*空出i原來所在的位置,輸出*/
for(k=j;k!=i-1;k--) /*將空格以前到i的正確位置之間的數(shù)字依次向后移動一格*/
{
b[c[k>=b[c[k-1>; /*數(shù)字向后移動*/
b[c[k-1>=0;
print();
}
b[c[k>=i; /*將中間的數(shù)字i移入正確的位置*/
b[4]=0; /*空出中間的空格*/
print();
break;
}
else if(b[c[j>==i) break; /*數(shù)字i在正確的位置*/
}
void print(void) /*按格式要求輸出矩陣*/
{
int c;
for(c=0;c<9;c++)
if(c%3==2) printf("%2d ",b[c]);
else printf("%2d",b[c]);
printf("----%2d----\n",count++);
}