ENIX007
高階會員
![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif)
![](images/icon_photo_none.gif) 發表:28 回覆:274 積分:185 註冊:2003-11-27
發送簡訊給我
|
各位好,最近在解決問題時衍生的數值分析問題,小弟有試著解出來,
只是一直無法分析出(完整)的解答,因此在此向各位請教
問題是這樣的:
1.給定一個基礎值Base
2.給定一個允許差值Allow,因此得出一串連續整數(基礎值加減允許差值)
3.給定一分析值Analysis
4.列出"所有"(2)所得連續整數列所能組合(限加法)成分析值的可能
例:
Base = 5,
Allow = 3,-->連續整數=2,3,4,5,6,7,8
Analysis = 20 結果:
20=
2*10,
2*8+4,
2*7+6,
2*6+8,
2*5+5*2,
2*4+4*3,
2*4+4*1+8...
注意:當Base < Allow時,連續整數列從1開始
例:
Base=5,Allow=6-->連續整數=1~11 有興趣的大大可以試試 ![]() 程式迷人之處,在於邏輯思考,然而卻也是惱人之處~~
------ 程式迷人之處,在於邏輯思考,然而卻也是惱人之處~~
|
ENIX007
高階會員
![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif)
![](images/icon_photo_none.gif) 發表:28 回覆:274 積分:185 註冊:2003-11-27
發送簡訊給我
|
這是小弟目前分析出來的程式,但僅限於2層,像20=2*4+4*1+8這種情形
就出不來了< >
考慮使用遞迴,只是複雜度會大大增加...對我來說< >
還是請有興趣的大大一起來試試看囉(好像沒人有興趣) ![]()
< class="code"> int Base = atoi(Edit1->Text.c_str());
int Allow = atoi(Edit3->Text.c_str());
int Analysis = atoi(Edit4->Text.c_str());
int type = 1;
int Min = Base-Allow;
int Max = Base Allow;
int work;
TListItem *item;
int i=0,j=0;
while (Min < Max)
{
work = Analysis;
if (work%Min == 0)
{
item = ListView1->Items->Add();
item->Caption = type;
item->SubItems->Add(IntToStr(Min) ":" IntToStr(work/Min));
type ;
i=1;
while (work-Min > Min)
{
work -= Min;
j ;
while (Min i < Max)
{
if (work%(Min i) == 0)
{
item = ListView1->Items->Add();
item->Caption = type;
item->SubItems->Add(IntToStr(Min) ":" IntToStr(j) "," IntToStr(Min i) ":" IntToStr(work/(Min i)));
type ;
}
i ;
}
i=1;
}
j=0;
}
else
{
while (work-Min > Min)
{
work -= Min;
j ;
while (Min i < Max)
{
if (work%(Min i) == 0)
{
item = ListView1->Items->Add();
item->Caption = type;
item->SubItems->Add(IntToStr(Min) ":" IntToStr(j) "," IntToStr(Min i) ":" IntToStr(work/(Min i)));
type ;
}
i ;
}
i=0;
}
j=0;
}
Min ;
}
見笑了 ![]() 程式迷人之處,在於邏輯思考,然而卻也是惱人之處~~
------ 程式迷人之處,在於邏輯思考,然而卻也是惱人之處~~
|
m8815010
版主
![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif)
![](images/icon_photo_none.gif) 發表:99 回覆:372 積分:289 註冊:2003-11-13
發送簡訊給我
|
引言:
各位好,最近在解決問題時衍生的數值分析問題,小弟有試著解出來,
只是一直無法分析出(完整)的解答,因此在此向各位請教
問題是這樣的:
1.給定一個基礎值Base
2.給定一個允許差值Allow,因此得出一串連續整數(基礎值加減允許差值)
3.給定一分析值Analysis
4.列出"所有"(2)所得連續整數列所能組合(限加法)成分析值的可能
例:
Base = 5,
Allow = 3,-->連續整數=2,3,4,5,6,7,8
Analysis = 20 結果:
20=
2*10,
2*8 4,
2*7 6,
2*6 8,
2*5 5*2,
2*4 4*3,
2*4 4*1 8...
注意:當Base < Allow時,連續整數列從1開始
例:
Base=5,Allow=6-->連續整數=1~11 有興趣的大大可以試試 程式迷人之處,在於邏輯思考,然而卻也是惱人之處~~
>>< face="Verdana, Arial, Helvetica"> ENIX007你好< >:不會呀,我覺得這題目滿有趣的呀,只是我現在才看到了^^!
這題符合演算法領域上題目的一個重要特點,就是題目簡單,但解答郤可能長篇大論,像費瑪最後定理就是最好的一個例子< >! After all,屁了一堆,我看你的中文題目有點看不是很懂,好像有點點不太嚴緊,我小小翻寫一下,你看看行不行哦< >:<>科學記號打不出來,改用文字折衷表達,將就將就囉< >> 題目:
given m、n、a 屬於 Z , where m > n >= 1
Set S(m,n) in Z , where S(m,n)={Xn,Xn 1,Xn 2,...,Xm-2,Xm-1,Xm}
for all m >= Xi >= n Xi=i suppose Set A={a1,a2,a3,...a(t-2),a(t-1),at} , and
for all ai (t >= i >= 1) in Set A: Condition1:
ai={b1,b2,...,b(u-1),bu} , if ai=b1 b2 ... b(u-1) bu ,
for all bj (u >=j >=1) in Set S(m,n)
and bi≠bj if i≠j
Condition2:
for all ai,aj in Set A , if i≠j , ai≠aj Find A=?
====================================================================================== So,這是我看你中文題目描述後,依據體會的義意翻寫的,你會發現我是這樣寫的:
ai={b1,b2,...,b(u-1),bu} , if ai=b1 b2 ... b(u-1) bu ,
for all bj (u >=j >=1) in Set S(m,n)
and bi≠bj if i≠j
因為你說只限加法,且我認為連續整列中的element是不可以重覆選取的(你沒說可不可以) 所以我認為(用你的sample):
20=5 7 8 -->OK
20=4 8 8 -->NG 因為元素重覆
20=2*7 6 -->NG 因為用到乘法了
你用乘法可能是表示重覆選取的意思?所以題目上我還不是很了解! After all,屁了一堆,還在問題目的意思 !
|
ENIX007
高階會員
![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif)
![](images/icon_photo_none.gif) 發表:28 回覆:274 積分:185 註冊:2003-11-27
發送簡訊給我
|
謝謝您的回應...
由於當初題目衍生自實際的工程問題,並非演算法,因此沒有嚴謹的定義,
還勞煩您長篇大論來問題目的意思,真抱歉 ![]()
實際題目是這樣的,假設某物品是以>這也是>
( >
想使用遞迴,不過始終無法將此問題抽絲剝繭的分析... > 程式迷人之處,在於邏輯思考,然而卻也是惱人之處~~
------ 程式迷人之處,在於邏輯思考,然而卻也是惱人之處~~
|
m8815010
版主
![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif)
![](images/icon_photo_none.gif) 發表:99 回覆:372 積分:289 註冊:2003-11-13
發送簡訊給我
|
引言:
PS.看到您使用正統的數學分析式,有點難以適應,真糟糕,才離開學校3年...
當兵果然是一劑可怕的孟婆湯 程式迷人之處,在於邏輯思考,然而卻也是惱人之處~~
>>< face="Verdana, Arial, Helvetica"> ENIX007你好 : 嗯,你說這是出自工程的問題,呵呵,我是不知道啦!不過根據我學 >!問題的典型解法就是要把解分為兩部份,先用我們先前討論的例子講說比較好了解(我已了解問題了): 例子簡單說就是 class="code">
對於A集合內所有的組成方法,可以為含2的(不管含幾個),和都不含2的,所以上式可寫成 T([2,8],20)=T([2,8],18) T([3,8],20)
含 不含 所以,有沒有感覺問題已經解了?因為T([2,8],18)和T([3,8],20)兩項又一直可以拆解下去,一直拆到最小...! 所以做個conclusion:
1.我想這樣寫來,recursively的觀念解問題已經再明白不過了吧(不論觀念或真的寫程式implement)
2.其實有這樣的一個等式出來的話,就可以求題目的Big O值了,這是最最最重要的,因為big O值關係你的程式是run到你隔天起床就結束,還是要run到人類上火星還在run,呵呵呵! 我偷攋的地方:
1.上列等式只是用我們的例子去列的,真正要列成通式才正式,這我就偷懶了,通式列完後,就可以算Big O值了。在離散數學的generating function那章有教,但我真忘了,呵呵!
2.偷懶不implement出程式碼了,我寫就太小看ENIX007你了,呵呵! 小小小小小淺見,參著參著參著! PS.當兵的確是消磨一個人鬥志的好時機!我當兵的晚,去年3月才退伍!服役時在陸總當文書兵(美稱),整天就是打雜,送文件、打字。我就想:媽的,我碩士你還讓我當兵就算了,書讀那麼高還叫我打字???哈哈哈,總之我當兵也是滿腹委曲就是了! 所以我想每個人都有這樣的經歷了! After all,希望你已經早早退伍了< >< > ! 發表人 -
|
ENIX007
高階會員
![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif)
![](images/icon_photo_none.gif) 發表:28 回覆:274 積分:185 註冊:2003-11-27
發送簡訊給我
|
版主您好
由於小弟目前工作繁忙,實在無法抽出時間來研究這個問題,在此先結案...
收到系統的警告信了< >
等工作告一段落,再來向您討教一番< >
希望到時候我已能將遞迴完成... PS.去年3月退喔...看來我們不是同梯就是兄弟梯了,小弟也是去年3月退,
不過我是大學畢業直接就進去了,研究所沒考上< >
現在已在公司做了一年多(也是我學程式的時間)
當兵真的是浪費時間...
總之,恭喜咱們都是退伍身< > 程式迷人之處,在於邏輯思考,然而卻也是惱人之處~~
------ 程式迷人之處,在於邏輯思考,然而卻也是惱人之處~~
|
m8815010
版主
![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif)
![](images/icon_photo_none.gif) 發表:99 回覆:372 積分:289 註冊:2003-11-13
發送簡訊給我
|
引言:
版主您好
由於小弟目前工作繁忙,實在無法抽出時間來研究這個問題,在此先結案...
收到系統的警告信了< >
等工作告一段落,再來向您討教一番< >
希望到時候我已能將遞迴完成... PS.去年3月退喔...看來我們不是同梯就是兄弟梯了,小弟也是去年3月退,
不過我是大學畢業直接就進去了,研究所沒考上< >
現在已在公司做了一年多(也是我學程式的時間)
當兵真的是浪費時間...
總之,恭喜咱們都是退伍身< > 程式迷人之處,在於邏輯思考,然而卻也是惱人之處~~
ENIX007你好 : 再補 >! >! >! 以下,附上我的 >: < class="code">
===================================================================
首先是問題的再確認,這很重要,如果不對就不用看下去了! Problem Def:
給定任意連續正整數的sequence,再給定任一正整數A,求連續整數sequence
組成A的方式共有幾種(可重覆) ex:sequence等於 2,3,4,5,6,7,8,A=20,求由2,3,4,5,6,7,8組成20的方式
共有幾種(可重覆) 由於方便討論所以我必需符號化問題,所以: sequence 表示成:[2,8]
A 表示成:sum
可求出最後所有解的function 表示成:T 所以最後我們要求 T([2,8],20)=?
通式化 T([mix,max],sum)=? where max>man>=1,and sum>=min ===================================================================
然後是演算法上(理論面)的解法,承接之前的回覆再補充說明,這邊一定要先透徹
了解,不然就不用再講coding的implement了! Algorithm: 對於A集合內所有的組成方法,可以分為含2的(不管含幾個),和都不含2的,所以上式可寫成: T([2,8],20)=T([2,8],18)+T([3,8],20) -------------------(1)
含2 不含2
重要,重要:分成兩組之後,這兩組是彼此獨立的哦! 再分下去: T([2,8],18)=T([2,8],16)+T([3,8],18) -------------------(2)
含2 不含2
T([3,8],20)=T([3,8],17)+T([4,8],20) -------------------(3)
含3 不含3
依此類推一直分下去:
....
...
.. 分到什麼時候停呢? 當T([min,max],sum)的 min>=sum時就停了,min=sum時,表示sum剛好可以由這樣的組
合法組合成,min
~~
TForm1 *Form1;
void FindRlt(int min,int max,int sum,TTreeNode* root); <---主要遞迴程式 //---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormCreate(TObject *Sender)
{
TTreeNode* Root;
Root=TreeView1->Items->AddChild(NULL,"Root"); FindRlt(2,8,6,Root); <---範例設sum=6,因為樹長的很大
}
//---------------------------------------------------------------------------
void FindRlt(int min,int max,int sum,TTreeNode* root)
{
if (sum==0) { <---sum=0表示切分法剛好成功
TTreeNode* Endchild;
Endchild=Form1->TreeView1->Items->AddChild(root,"END");
return;
} if (min>sum) { <---min>sum表示切分法失敗
TTreeNode* Errchild;
Errchild=Form1->TreeView1->Items->AddChild(root,"ERR");
}
else { <---minTreeView1->Items->AddChild(root,"0");
Rchild=Form1->TreeView1->Items->AddChild(root,IntToStr(min)); FindRlt(min+1,max,sum,Lchild);
FindRlt(min,max,sum-min,Rchild);
}
}
就這樣,簡單的幾行就可以辦到好,長出來的樹就是所有解,下圖是我用T([2,8],6)的範例之
解,因為2元樹長大的很快,所以要更大的例子就自行測試。 那重要是不曉得這樣從2元樹看解有沒有問題? 方法就是從root到任一個leaf都是一種分法,如果是ERR表示分法錯誤,如果是END表示分法成功
,成功的分法我們就把組成的元素全部抽出來,抽出的方法就是從root travel到一個END的leaf
然後把中間遇到的數字都抽出! 例如上圖紅線處是一條由root走到END leaf的路徑,途中經過數字2和4(數字0不管),所以可得
解:
6 = 2 + 4
===================================================================
結論: 1.上述只找一條解,要窮舉其它2元樹上的解應該可以略了吧 ?
>!
>!
===================================================================
<>打屁一下:>
喔,
|
ENIX007
高階會員
![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif) ![](./myimg/board/mystar.gif)
![](images/icon_photo_none.gif) 發表:28 回覆:274 積分:185 註冊:2003-11-27
發送簡訊給我
|
引言: 喔,ENIX007你也是3月退的!我的役期是1年8個月(是扣成功領和軍訓各一個月),
所以我去年3月退,1878梯的。ENIX007你如果也是3月退的話,應該梯數比我大,
因為依你的年紀應該沒有扣成功領才對,所以大概是1876梯 - 1梯左右,呵呵,
對嗎??? ENIX007你資料上寫從事遊戲相關設計,不曉得方便不方便說一下你的公司,以及
公司做什麼的?因為我對遊戲也很有興趣,而且最近也想換個工作,所以....... 方不方便都沒關係哦,反正隨便聊聊,呵呵呵!
版主您好:
先談正事
分析之後果然 > 打屁部分:
小弟是 >
選兵時被海巡署挑走,千萬別以為海巡很爽喔,自殺逃兵的也是一堆,因為我是
戰情兵,每天都在處理這些案件,所以比較了解...
至於工作,小弟在高雄某遊戲研發公司,目前製作線上遊戲...(範圍應該很小了)< > 程式迷人之處,在於邏輯思考,然而卻也是惱人之處~~
------ 程式迷人之處,在於邏輯思考,然而卻也是惱人之處~~
|