推 hikaru4:看的很吃力 有個小問題 sum123難道不會溢位溢到變正的嗎？ 10/23 20:08
→ hikaru4:還是我還沒真正看懂？ 10/23 20:10
→ hikaru4:噗....好像看懂了 是相加的不會溢到變正？ 是這樣嗎？ 10/23 20:11
推 chhsiao:是兩個介於 0 - 2^31-1 的正數相加喔! 10/23 21:08
※ 引述《JingXD (@O@)》之銘言：
: 使徒四的第二個測資....
: 為什麼連 用三個FOR 去一一檢查 也不對阿 囧囧囧
: WHY WHY WHY ~~~ 囧囧
這是我的 loop 版本:
#include <stdio.h>
int main(){
int N;
int A, B, C, D;
int a, b, c;
int i, j, k;
int sum1, sum2, sum3;
int found;
for(scanf("%d", &N); N > 0; --N){
scanf("%d %d %d %d %d %d %d", &D, &a, &b, &c, &A, &B, &C);
found = 0;
for(i = 0, sum1 = 0; !found && i <= a &&
sum1 >= 0 && sum1 <= D; ++i, sum1 += A)
for(j = 0, sum2 = sum1; !found && j <= b &&
sum2 >= 0 && sum2 <= D; ++j, sum2 += B)
for(k = 0, sum3 = sum2; !found && k <= c &&
sum3 >= 0 && sum3 <= D; ++k, sum3 += C)
if(sum3 == D)
found = 1;
printf(found ? "yes\n" : "no\n");
}
return 0;
}
其中 sum1 代表用到的 alligator legs 的魔力總和,
sum2 代表用到的 alligator legs 及 bat eyes 的魔力總和,
sum3 代表用到的 alligator legs, bat eyes 及 cat skulls 的魔力總和.
我來說一下什麼是 "溢位" 好了:
因為 int 只有 32 bits 可以用, 所以只能表示 -2^31 ~ 2^31 - 1,
也就是 -2147483648 ~ 2147483647.
當兩個正數相加的結果超過 2147483647 後,
就發生所謂的 "溢位", 這時多出來的那 1 個 bit 會被丟掉,
剩下來的 bits 在電腦解讀起來會變成負數 (注意只有兩個正數相加才會這樣),
可以想像成下圖:
|-------------------------------o----------------------*--------|
-2^31 A 2^31-1
|-------------------------------o-------------------------*-----|
-2^31 B 2^31-1
|---------------*---------------o-------------------------------|
-2^31 A+B 2^31-1
因此, 我用 sumX >= 0 來克服 overflow 的問題.
因為 D <= 2147483647, 因此 sumX 加到 overflow 的話,
就一定超過 D 了.
---
這是不好的示範, 大家不要學 XD
--
>_<
U
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.54