xdoj五星題172 構造運算式
標題
構造運算式
類別
綜合
時間限制
1S
記憶體限制
100Kb
問題描述
給定一個表示序列長度的整數n（3<=n<=9)，在序列1 2 3…n中插入‘＋’，‘－’，‘ ’構造運算式，插入‘ ’表示前后兩個數字構成一個整數，例如1 2 -3 -4 -5=0，
輸出構造的所有運算式中，結果為0的運算式的數量，例如n=3時，只有運算式1+2-3=0，輸出結果為1，
輸入說明
輸入資料為一個整數n（n<10），表示序列長度，同時表示輸入序列為“1 2 3…n”，
輸出說明
對于每一組資料，輸出一個整數，表示構造的運算式中結果為0的運算式數量，
輸入樣例
3
輸出樣例
1
題目思路：
想用遞回的方法來整這個題，
快捷的數學方法我是想不到了（QAQ）
目前只想出兩種方法：
**1.**將n個數之間的n-1個空格轉換成三進制，用0代表+，用1代表-，用2代表“ ”，這樣相當于是給了輸入然后用函式去算這個運算式，省去了遞回的程序，只需要遍歷即可，
**2.**我自己用的遞回，從第一個數開始壓堆疊，之后判斷這個數之后的符號，如果是加減直接去搜索后一位數，把這個數放在其后的位置就可以了，
如果是空格比較麻煩，這時候要用一個head和tail，分別表示他的首尾（用來處理連續的空格），然后每放進一個去，就讓前面的×10，100，1000……（看具體前面有多少個空格，這個長度可以用tail-head來計算），
在寫這部分代碼的時候，有幾點我修改的比較多：
1.在什么時候改變point和tail，讓他們指向下一個點進行修改，
2.在for回圈的開始還是結尾去判斷是否已經搜索到底（最后寫在開頭）；
3.關于head的位置，如果不寫那個while回圈，他會每次都少一塊，所以通過while回圈讓head移動到第一個后面是空格的位置，
4.在除錯的時候，會出現多余幾次的加和（其實對結果沒啥影響，就是多運行了幾次），所以我就在最后加了一個a[n]！=0，其實也沒啥用，
5.對tail、point和head的移動處理，我也是邊試邊寫的，程序的話還是自己畫畫草圖吧，
其實題也不算特別特別難（往往做完之后都這么覺得），還是對遞回回去各個數的改變太不熟悉了……一定多練題！！（大概）
ps：xdoj上反正提交是不給評判，管他的呢，反正自己有識訓，oj算個xxxxx……
ps2:第二天試了一下都能AC，兩個代碼都可以
代碼是遞回思路寫的，先附上自己的代（亂）碼：
#include<stdio.h>
int a[20]={0};
int head=1,tail=1;
int point=1;
int n;
int ans=0;
int main()
{
void dfs(int);
scanf("%d",&n);
a[1]=1;
dfs(1);
printf("%d",ans);
}
void dfs(int point)
{
int i,j;
for(i=1;i<=3;i++)
{
if(point==n)
break;
if(i==1)//此處為+
{
point++;
a[point]=point;
tail=point;
head=tail;
dfs(point);//在這里遞回
a[point]=0;//這一部分是用來進行改變的
point--;
tail--;
if(head>tail)
head=tail;
continue;
}
if(i==2)//這里是- ，和+基本一樣
{
point++;
a[point]=-point;
tail=point;
head=tail;
dfs(point);
a[point]=0;
point--;
tail--;
if(head>tail)
head=tail;
continue;
}
if(i==3)//這里是空格，最難寫的地方
{
point++;
tail=point;
int lenth=1;
while(a[head-1]>=10||a[head-1]<=-10)//這是用來找第一個空格位置的，把head指過去
head--;
for(j=tail;j>=head;j--)//分正負進行討論
{
if(a[head]<0)
a[j]=-j*lenth;
if(a[head]>0)
a[j]=j*lenth;
lenth*=10;
}
dfs(point);
a[point]=0;
point--;
tail--;
if(head>tail)//這個處理突發奇想，防止head在tail后面
head=tail;
continue;
}
}
int sum=0;
for(j=1;j<=n;j++)
sum+=a[j];
if(sum==0&&a[n]!=0)//其實第二個沒啥用，是自己代碼爛了，打個補丁
ans++;
}
代碼有不好或者繞彎路的地方太正常了，我還只是個剛學c語言的大一弱雞，求放過~
另一種非遞回轉三進制的方法有室友寫了，我就不再整活了，放一下：
xdoj-172 構造運算式 ——snow_cx
億點感慨：
從下午七點寫到晚上1點，雖然不難吧但是對于不熟練的我真的是瘋狂折磨，在除錯中度過一晚上，不過還好，至少學到東西了吧（而且有人陪著寫也沒那么累），而且，竟然有人看我博客？本來是寫了給自己看的，結果不知道哪位大聰明找到這里來了（HAHAHA~)
ps3:這算不算dfs？我也不是很清楚😂，叫什么的吧反正是遞回就完事了（手動狗頭）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/241507.html
標籤：其他
下一篇：java面向物件