Re: [理工] [離散]-97中山資工

[monkeykej (真是個麻煩)]

※ 引述《GraffitiK (GraffitiK)》之銘言：
http://www.lib.nsysu.edu.tw/exam/master/eng/infoe/infoe_97.pdf

想請問97中山資工離散
第1題：
寫成等式33x+29y=2490，利用Euclidean algorithm求整數x,y
我最後寫成一般式2490=29[2490(8-33k)]+33[2490(-7+29k)]
                    =29(19920-82170k)+33(-17430+72210k), 對所有k屬於Z
x=-17430+72210k, y=19920-82170k
到這裡就卡住了... 不知道怎麼取k使x,y>=0...

解答是寫成2490=33(-7x2490)+29x(8x2490)
              =33(-17430+29k)[phone]k), 對所有k屬於Z
x=-17430+29k, y=19920-33k
當k=602 or 603時x,y>=0

是我的算式寫錯了嗎？



→ GraffitiK:喔 對, 是改變奇數次才open, 我寫錯了. 第1題是因為
→ GraffitiK:1=29(8-33k)+33(-7+29k), 兩邊乘2490後就變成我寫的那樣
→ GraffitiK:這樣有錯嗎? 可是像小黃離散p.1-51例33也是類似的算法不
→ GraffitiK:是嗎...?
抱歉我沒上過他的課(￣□￣|||)a

但就算式而言，1=29(8-33k)+33(-7+29k)

可以看出1=29*8+33*(-7)

左右乘2490得到x=(-7)*2490，y=8*2490為一個解

故得之通解為x = (-7)*2490+ 29k ，y=8*2490 -33k

再依題意，x、y為非負整數

故k僅可能為602、603

我不明白為什麼要把+29跟-33也放大這麼多倍= =

這樣會跳過很多解

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.25.160
推 GraffitiK:好的 謝謝你, 不過我已經在小黃書上找到兩題用這樣我原
→ GraffitiK:本那種做法了... 蠻疑惑哪裡出了問題...為什麼放大後就
→ GraffitiK:求不出正確的值...(@_@)a
推 ohstar:monkey是對的 要先找到一個解再去配出通解
→ ohstar:你先配通解再放大 跳的間隔就會變大