1. PTT
  2. Grad-ProbAsk

[理工] 中央106资演［5］

楼主: w831231 (tsai)   2018-02-08 07:24:11
感觉第五题等等会考
但是该怎么証呢 拜托大家了@@
https://i.imgur.com/sfoIjSa.jpg
作者: leoone (里欧一代)   2018-02-08 08:02:00
证Y不属于NP但是是NP complete
楼主: w831231 (tsai)   2018-02-08 08:39:00
可讲的详细点吗 谢谢
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 08:40:00
就把你证明的方法跟理论基础讲出来呀
作者: pinchieh1996 (PinJJ)   2018-02-08 08:41:00
搜105 中央 有一篇在对答案一模一样的题目
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 08:42:00
她问你要怎么证明y是hp hard你就把证法讲一下就好
楼主: w831231 (tsai)   2018-02-08 08:42:00
谢谢大大门
楼主: w831231 (tsai)   2018-02-08 08:44:00
回p大 似乎没有欸 https://i.imgur.com/gW7zvOQ.jpg
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 08:44:00
所以只要把x reduce到y就代表你可以吧所有的np reduce到y 如此得证y是np hard
作者: lion83395 (阿月)   2018-02-08 08:45:00
https://i.imgur.com/P2TbCex.jpg
楼主: w831231 (tsai)   2018-02-08 08:46:00
感谢感谢
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 08:46:00
把p, np, np complete, np hard定义搞清楚就没这么难了
作者: leoone (里欧一代)   2018-02-08 08:58:00
中央很爱考 这四年考了3年 真的不会就背起来吧
作者: gR7P4zXH (tpn7gpdx)   2018-02-08 09:07:00
好
作者: agag5123 (ag)   2018-02-08 11:16:00
干 考完马上发现脑残了，最后最短路径算法是小于
作者: moneylon (bencool)   2018-02-08 11:18:00
你是说20.21题吗
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 11:19:00
最后是我才学术浅吗我不知道大于要怎么做不对应该是我他的选项大小于跟我想的相反
作者: gR7P4zXH (tpn7gpdx)   2018-02-08 11:20:00
先知
作者: moneylon (bencool)   2018-02-08 11:20:00
对 我也是 我觉得是大于 可是选项没有...
作者: devilkool (对猫毛过敏的猫控)   2018-02-08 11:21:00
我也想半天想不出哪个选项能选 求解
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 11:21:00
然后我抓到他heap sort那个建heap他写错应该是i--
作者: moneylon (bencool)   2018-02-08 11:22:00
对
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 11:22:00
我当作题目大于小于写反了在答
作者: tcc080206 (雪ノ下雪乃俺の嫁)   2018-02-08 11:22:00
还有quicksort A[i]应该找>pivot，A[j]应该是<pivot的吧。然后用adjust调整heap，后面不是应该是i--吗？
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 11:23:00
整体而言不难 话说河内塔是39吗我找不到更短的
作者: tcc080206 (雪ノ下雪乃俺の嫁)   2018-02-08 11:24:00
39+1
作者: agag5123 (ag)   2018-02-08 11:24:00
我也是39
作者: age01282005 (咖啡〃)   2018-02-08 11:25:00
1+7+31=39
作者: havewind   2018-02-08 11:26:00
河内塔也算39
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 11:26:00
他选想给不好 有给40的话我会不小心选到ww
作者: wei5280 (wei5280)   2018-02-08 11:28:00
那个i++怎么算啊 这样是送分吗
作者: shownlin (哈哈阿喔)   2018-02-08 11:28:00
最后一题bellman ford是不是怪怪的
作者: agag5123 (ag)   2018-02-08 11:28:00
除3的那个sort复杂度是多少啊？
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 11:30:00
做后一题不是floyd warshall吗tn=3t(2n/3) 我印象中时间递回涨这样
作者: microchianag (Sss11234 116EE)   2018-02-08 11:32:00
先知
作者: moneylon (bencool)   2018-02-08 11:32:00
logn 3/2的3. 我写这样
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 11:32:00
我觉得建立heap不会送不过最后几题就不知道了
作者: agag5123 (ag)   2018-02-08 11:32:00
谢谢 我也是选那项
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 11:33:00
空间是n吗
作者: moneylon (bencool)   2018-02-08 11:33:00
所以T大的i写 i=n/2吗
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 11:34:00
对啊虽然+1跟没加执行结果应该是一样的
作者: HungDa (hongren)   2018-02-08 11:35:00
额外空间有需要n？
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 11:35:00
我算了stack用的空间想说到底是多少不过现在想想应该小于n要应该也是log的等级应该是logn现在想了一下
作者: lion83395 (阿月)   2018-02-08 11:37:00
我写Logn 不过不是很确定
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 11:38:00
我那时不小心连array也存到stack就变n了QQ
作者: king8313   2018-02-08 11:38:00
我也在犹豫递回用的空间要不要算
作者: leoone (里欧一代)   2018-02-08 11:39:00
我怎么觉得我中央有点爆炸 第一题写log2 3QQ
作者: Xunion (Xun)   2018-02-08 11:41:00
你不可以有台大了就这样让分r
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 11:42:00
有台大就很嚣张QQ
作者: leoone (里欧一代)   2018-02-08 11:44:00
别说台大惹 想到就伤心
作者: jimmy45689 (kble)   2018-02-08 11:45:00
想问一下np那几题答案多少 我有连续两题写abce 因为当初有点想放没读很熟
作者: moneylon (bencool)   2018-02-08 11:46:00
leo大台大电机比80%的人多10分 2^10000
作者: ReanoX (ReanoX)   2018-02-08 11:47:00
Stack的空间不用算吗？我选n呢QQ
作者: leoone (里欧一代)   2018-02-08 11:48:00
可4马跟asymmetric错惹 -15
作者: djmez   2018-02-08 11:48:00
至少有两题程式码有问题 只是连考卷都收走了让你也没办法
作者: ReanoX (ReanoX)   2018-02-08 11:49:00
而且那题Heap看到i ++我直接选I=0不要进for XD
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 11:50:00
你不能跟教授打错字过不去啊XD
作者: djmez   2018-02-08 11:51:00
河内塔根本懒的算 直接放了
作者: HungDa (hongren)   2018-02-08 11:54:00
中央教授好爽电脑阅卷都不用改,而且自己应该没对过考卷
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 11:55:00
不错了 跟昨天的电机丙比...
作者: moneylon (bencool)   2018-02-08 11:56:00
别提那四只马了
作者: gR7P4zXH (tpn7gpdx)   2018-02-08 11:57:00
????
作者: harryboy23 (BB's布里斯)   2018-02-08 12:05:00
河内塔好像是把12345叠在B后 6移到C 7回合 再移动12345就好 所以是7+2^5-1=38 ？？
作者: shownlin (哈哈阿喔)   2018-02-08 12:11:00
对 floyd-warshall 打错XD
作者: HungDa (hongren)   2018-02-08 12:17:00
话说我看到有人带整本算法来看整个眼神死
作者: agag5123 (ag)   2018-02-08 12:17:00
123放在45上就要7步了。另外heap那题我直接背诶，印象中是从最后一个父点作adjust
作者: djmez   2018-02-08 12:21:00
可是他一直加加还>0 不给结束了
作者: Dora5566 (咩休干某)   2018-02-08 12:22:00
应该是i--打错成i++
作者: MOUOREO (毛毛)   2018-02-08 16:22:00
123放到45 要7步 然后6放到最右边一步再加31 共39步？
作者: jacky804024 (HsuYo)   2018-02-08 18:07:00
Leo大 有台大了 中央就乱考
作者: leoone (里欧一代)   2018-02-09 00:14:00
到底是谁说我有台大QQ 我自己怎都不知道
作者: leoone (里欧一代)   2018-02-08 16:02:00
证Y不属于NP但是是NP complete
楼主: w831231 (tsai)   2018-02-08 16:39:00
可讲的详细点吗 谢谢
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 16:40:00
就把你证明的方法跟理论基础讲出来呀
作者: pinchieh1996 (PinJJ)   2018-02-08 16:41:00
搜105 中央 有一篇在对答案一模一样的题目
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 16:42:00
她问你要怎么证明y是hp hard你就把证法讲一下就好
楼主: w831231 (tsai)   2018-02-08 16:42:00
谢谢大大门
楼主: w831231 (tsai)   2018-02-08 16:44:00
回p大 似乎没有欸 https://i.imgur.com/gW7zvOQ.jpg
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 16:44:00
所以只要把x reduce到y就代表你可以吧所有的np reduce到y 如此得证y是np hard
作者: lion83395 (阿月)   2018-02-08 16:45:00
https://i.imgur.com/P2TbCex.jpg
楼主: w831231 (tsai)   2018-02-08 16:46:00
感谢感谢
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 16:46:00
把p, np, np complete, np hard定义搞清楚就没这么难了
作者: leoone (里欧一代)   2018-02-08 16:58:00
中央很爱考 这四年考了3年 真的不会就背起来吧
作者: gR7P4zXH (tpn7gpdx)   2018-02-08 17:07:00
好
作者: agag5123 (ag)   2018-02-08 19:16:00
干 考完马上发现脑残了，最后最短路径算法是小于
作者: moneylon (bencool)   2018-02-08 19:18:00
你是说20.21题吗
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 19:19:00
最后是我才学术浅吗我不知道大于要怎么做不对应该是我他的选项大小于跟我想的相反
作者: gR7P4zXH (tpn7gpdx)   2018-02-08 19:20:00
先知
作者: moneylon (bencool)   2018-02-08 19:20:00
对 我也是 我觉得是大于 可是选项没有...
作者: devilkool (对猫毛过敏的猫控)   2018-02-08 19:21:00
我也想半天想不出哪个选项能选 求解
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 19:21:00
然后我抓到他heap sort那个建heap他写错应该是i--
作者: moneylon (bencool)   2018-02-08 19:22:00
对
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 19:22:00
我当作题目大于小于写反了在答
作者: tcc080206 (雪ノ下雪乃俺の嫁)   2018-02-08 19:22:00
还有quicksort A[i]应该找>pivot，A[j]应该是<pivot的吧。然后用adjust调整heap，后面不是应该是i--吗？
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 19:23:00
整体而言不难 话说河内塔是39吗我找不到更短的
作者: tcc080206 (雪ノ下雪乃俺の嫁)   2018-02-08 19:24:00
39+1
作者: agag5123 (ag)   2018-02-08 19:24:00
我也是39
作者: age01282005 (咖啡〃)   2018-02-08 19:25:00
1+7+31=39
作者: havewind   2018-02-08 19:26:00
河内塔也算39
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 19:26:00
他选想给不好 有给40的话我会不小心选到ww
作者: wei5280 (wei5280)   2018-02-08 19:28:00
那个i++怎么算啊 这样是送分吗
作者: shownlin (哈哈阿喔)   2018-02-08 19:28:00
最后一题bellman ford是不是怪怪的
作者: agag5123 (ag)   2018-02-08 19:28:00
除3的那个sort复杂度是多少啊？
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 19:30:00
做后一题不是floyd warshall吗tn=3t(2n/3) 我印象中时间递回涨这样
作者: microchianag (Sss11234 116EE)   2018-02-08 19:32:00
先知
作者: moneylon (bencool)   2018-02-08 19:32:00
logn 3/2的3. 我写这样
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 19:32:00
我觉得建立heap不会送不过最后几题就不知道了
作者: agag5123 (ag)   2018-02-08 19:32:00
谢谢 我也是选那项
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 19:33:00
空间是n吗
作者: moneylon (bencool)   2018-02-08 19:33:00
所以T大的i写 i=n/2吗
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 19:34:00
对啊虽然+1跟没加执行结果应该是一样的
作者: HungDa (hongren)   2018-02-08 19:35:00
额外空间有需要n？
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 19:35:00
我算了stack用的空间想说到底是多少不过现在想想应该小于n要应该也是log的等级应该是logn现在想了一下
作者: lion83395 (阿月)   2018-02-08 19:37:00
我写Logn 不过不是很确定
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 19:38:00
我那时不小心连array也存到stack就变n了QQ
作者: king8313   2018-02-08 19:38:00
我也在犹豫递回用的空间要不要算
作者: leoone (里欧一代)   2018-02-08 19:39:00
我怎么觉得我中央有点爆炸 第一题写log2 3QQ
作者: Xunion (Xun)   2018-02-08 19:41:00
你不可以有台大了就这样让分r
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 19:42:00
有台大就很嚣张QQ
作者: leoone (里欧一代)   2018-02-08 19:44:00
别说台大惹 想到就伤心
作者: jimmy45689 (kble)   2018-02-08 19:45:00
想问一下np那几题答案多少 我有连续两题写abce 因为当初有点想放没读很熟
作者: moneylon (bencool)   2018-02-08 19:46:00
leo大台大电机比80%的人多10分 2^10000
作者: ReanoX (ReanoX)   2018-02-08 19:47:00
Stack的空间不用算吗？我选n呢QQ
作者: leoone (里欧一代)   2018-02-08 19:48:00
可4马跟asymmetric错惹 -15
作者: djmez   2018-02-08 19:48:00
至少有两题程式码有问题 只是连考卷都收走了让你也没办法
作者: ReanoX (ReanoX)   2018-02-08 19:49:00
而且那题Heap看到i ++我直接选I=0不要进for XD
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 19:50:00
你不能跟教授打错字过不去啊XD
作者: djmez   2018-02-08 19:51:00
河内塔根本懒的算 直接放了
作者: HungDa (hongren)   2018-02-08 19:54:00
中央教授好爽电脑阅卷都不用改,而且自己应该没对过考卷
作者: TMDTMD2487 (ㄚ冰)   2018-02-08 19:55:00
不错了 跟昨天的电机丙比...
作者: moneylon (bencool)   2018-02-08 19:56:00
别提那四只马了
作者: gR7P4zXH (tpn7gpdx)   2018-02-08 19:57:00
????
作者: harryboy23 (BB's布里斯)   2018-02-08 20:05:00
河内塔好像是把12345叠在B后 6移到C 7回合 再移动12345就好 所以是7+2^5-1=38 ？？
作者: shownlin (哈哈阿喔)   2018-02-08 20:11:00
对 floyd-warshall 打错XD
作者: HungDa (hongren)   2018-02-08 20:17:00
话说我看到有人带整本算法来看整个眼神死
作者: agag5123 (ag)   2018-02-08 20:17:00
123放在45上就要7步了。另外heap那题我直接背诶，印象中是从最后一个父点作adjust
作者: djmez   2018-02-08 20:21:00
可是他一直加加还>0 不给结束了
作者: Dora5566 (咩休干某)   2018-02-08 20:22:00
应该是i--打错成i++
作者: MOUOREO (毛毛)   2018-02-09 00:22:00
123放到45 要7步 然后6放到最右边一步再加31 共39步？
作者: jacky804024 (HsuYo)   2018-02-09 02:07:00
Leo大 有台大了 中央就乱考
作者: leoone (里欧一代)   2018-02-09 08:14:00
到底是谁说我有台大QQ 我自己怎都不知道
继续阅读
[商管] 线代wangborwai[理工] 107 台大电机丙 离散Ryspon[理工] 资结 递回程式的时间复杂度ZChung[理工] 107台大电机计组leoone[理工] 106中央 线代jimmy45689[理工] 台大电机丙 离散moneylon[理工] 台联电子学wade4ever[理工] 基本气泡排序问题wayneshiau[心得] 台大资工 DoneDora5566[商管] 中央基数wangborwai

Links booklink

Contact Us: admin [ a t ] ucptt.com