題目如下,解法可能不是最好的? 若有更好解法? 請賜教?
初學算法~望多多指教啊~~
解法:
? 1?
??2?
??3?
#include?<iostream>
??4?
#include?<windows.h>
??5?
??6?
#define?MAXINPUT?15
??7?
??8?
using?namespace?std?;
??9?
?10?
struct?stack?{
?11?
????int?*data?;
?12?
????stack?*next?;
?13?
}?;
?14?
?15?
?16?
?17?
stack?*push(stack?*top?,?int?*data?)???//壓棧
?18?
{
?19?
????stack?*tem?=??new?stack?;
?20?
????
?21?
????tem->data?=?data?;
?22?
?23?
????tem->next?=?top?;
?24?
?25?
????return?tem?;
?26?
}
?27?
?28?
stack?*pop(stack?*top?,?int?**data)???//出棧
?29?
{????
?30?
????if(?top?==?NULL)
?31?
????????return?top?;
?32?
????stack?*tem?;
?33?
?34?
????tem?=?top?;
?35?
?36?
????*(data)?=?tem->data?;
?37?
?38?
????top?=?top->next?;
?39?
?40?
????delete?tem?;
?41?
?42?
????return?top?;
?43?
}
?44?
?45?
void?stackprint(stack?*top)??//打印棧內容
?46?
{
?47?
????while(1)
?48?
????{
?49?
????
?50?
????if(?top?==?NULL?)
?51?
????????break?;
?52?
?53?
????cout<<*(top->data)<<"?"?;
?54?
????
?55?
????top?=?top->next?;
?56?
????
?57?
????}
?58?
?59?
????cout<<endl?;
?60?
}
?61?
?62?
?63?
?64?
int?sum?=?0?,?input[MAXINPUT]?=?{0}??;
?65?
?66?
int?main(void)
?67?
{
?68?
????int?count?=?0?,?T?=?0?;
?69?
?70?
????cout<<"請輸入T值"<<endl?;
?71?
????cin>>T?;
?72?
?73?
????cout<<"請輸入w數組數目"<<endl?;
?74?
????cin>>count?;
?75?
????
?76?
????if(?count?>?MAXINPUT?)
?77?
????{
?78?
????????cout<<"輸入溢出"<<endl?;
?79?
????????return?1?;
?80?
????}
?81?
?82?
????for(?int?i?=?0?;?i?<?count?;?i++?)
?83?
????{
?84?
????????cout<<"請輸入w["<<i<<"]值"<<endl?;
?85?
????????cin>>input[i]?;
?86?
????}
?87?
?88?
????cout<<endl<<"Loading
"<<endl?;
?89?
????
?90?
?91?
?92?
????stack?*top?=?NULL?;??//初始化棧
?93?
?94?
????int?i?=?0??,?*temdata?=?input?,?*popdata?=?input?,?*enddata?=?&input[count]??;
?95?
?96?
????/*
?97?
????棧的非遞歸調用,
?98?
????先壓棧數據,然后依次遍歷剩余的數據,滿足條件打印,小于預期值就壓棧
?99?
????接著遍歷剩余數據,遍歷這個層次的數據完了就出棧,然后指針+1(指向下一個數據),繼續遍歷剩余數據
100?
????*/
101?
????
102?
????while(1)
103?
????{
104?
????????sum?+=?*temdata?;
105?
????????
106?
????????top?=?push(top?,?temdata)?;
107?
????
108?
????????if(?sum?==?T?)
109?
????????{
110?
????????????stackprint(top)?;
111?
????????????top?=?pop(top,&popdata)?;
112?
????????????sum?-=?*popdata?;
113?
????????????top?=?pop(top?,?&popdata?)?;
114?
????????????sum?-=?*popdata?;
115?
????????????temdata?=?++popdata?;????????
116?
????????
117?
????????}
118?
????????else?if?(sum?>?T?)
119?
????????{
120?
????????????top?=?pop(top,&popdata)?;
121?
????????????sum?-=?*popdata?;
122?
????????????temdata?=?++popdata?;
123?
????????}
124?
????????else?if(?sum<T?)
125?
????????{
126?
????????????temdata?=?++popdata?;
127?
????????}
128?
129?
????????if(?(temdata-1)?==?enddata?)
130?
????????{
131?
????????????top?=?pop(top,&popdata)?;
132?
????????????sum?-=?*popdata?;????????????
133?
????????????top?=?pop(top,&popdata)?;
134?
????????????sum?-=?*popdata?;
135?
136?
????????????temdata?=?++popdata?;
137?
????????}
138?
????
139?
????????if(?top?==?NULL?&&??popdata?==?enddata)
140?
????????????????break?;
141?
????
142?
????}
143?
144?
145?
146?
????
147?
????system("pause")?;
148?
149?
????return?1;
150?
151?
}
152?
153?
154?