发现一位专门用SQL解各种谜题的高人！

newkid

udfrog 发表于 2012-8-1 22:11
其实进行更好的数学建模是第一步，比如1楼时候的exchange 1 dollar题目，所谓的最直接了当的做法，把1分硬币 ...

1分是特例，这里只是为了展示其原理。
其实这道题有更好的递归解法，可以算几百块的分解方法。你想想看？

udfrog

newkid 发表于 2012-8-1 22:57
1分是特例，这里只是为了展示其原理。
其实这道题有更好的递归解法，可以算几百块的分解方法。你想想看？ ...

morning，nk，好的，明天我想想，睡了。。

newkid

udfrog 发表于 2012-8-1 23:04
morning，nk，好的，明天我想想，睡了。。

别睡，新的puzzleup出来了，等会翻译。

udfrog

newkid 发表于 2012-8-1 22:57
1分是特例，这里只是为了展示其原理。
其实这道题有更好的递归解法，可以算几百块的分解方法。你想想看？ ...

郁闷，以后睡前再也不合计问题了。不到5点就醒了，满脑子都是硬币。。。你所说的递归是这样的么？

1. with t as (
   
2. select (rownum-1)*50 val, 50 id from dual connect by rownum <=3 union all
   
3. select (rownum-1)*25 val, 25 id from dual connect by rownum <=5 union all
   
4. select (rownum-1)*10 val, 10 id from dual connect by rownum <=11 union all
   
5. select (rownum-1)*5 val, 5 id from dual connect by rownum <=21),
   
6. tmp1 as (
   
7. select        connect_by_root(val) + val val, id
   
8. from        t
   
9. where        id=25
   
10. start with id=50
    
11. connect by prior id>id and prior val<=100-val),
    
12. tmp2 as (
    
13. select        connect_by_root(val) + val val, id
    
14. from        (select * from t where id<=10 union all select * from tmp1)
    
15. where        id=10
    
16. start with id=25
    
17. connect by prior id>id and prior val<=100-val),
    
18. tmp3 as (
    
19. select        connect_by_root(val) + val val, id
    
20. from        (select * from t where id<=5 union all select * from tmp2)
    
21. where        id=5
    
22. start with id=10
    
23. connect by prior id>id and prior val<=100-val)
    
24. select count(*) from tmp3;
    

复制代码

newkid

udfrog 发表于 2012-8-2 10:42
郁闷，以后睡前再也不合计问题了。不到5点就醒了，满脑子都是硬币。。。你所说的递归是这样的么？

不是，我说的是逐渐增加硬币种类的做法。
只有1分：很容易得到0-100的组合数。
增加1个2分，2个2分，3个2分，... 直至50个。只需在前面基础上做加法，这样你得到了硬币种类<=2的所有组合数。
再增加5分硬币，同样道理。
用PLSQL很好做，SQL也可以试试。

udfrog

newkid 发表于 2012-8-2 11:18
不是，我说的是逐渐增加硬币种类的做法。
只有1分：很容易得到0-100的组合数。
增加1个2分，2个2分，3个 ...

没错，我躺着的时候就是这么合计的，我也觉得plsql更好而且效率应该更高，不过这个就是我用这个思想实现的sql写法，很奇怪的是，我在测试change 10dollar的性能时，会跑不出来。等弄完puzzleup那个题，我再看看

udfrog

1. declare
   
2. cnt        int:=0;
   
3. r        int:=0;
   
4. C        int:=&how_much_dollar_to_change;
   
5. begin
   
6.         for i in 0 .. 2*C loop
   
7.                 for j in 0 .. 4*C loop
   
8.                         for k in 0 .. 10*C loop
   
9.                                 exit when i*50+j*25+k*10>100*C;
   
10.                                 r:=100*C-(i*50+j*25+k*10);
    
11.                                 cnt:=cnt+r/5+1;
    
12.                         end loop;
    
13.                 end loop;
    
14.         end loop;
    
15.         dbms_output.put_line(cnt);
    
16. end;
    
17. /
    

复制代码

mark一下，这个代码兑换100dollar要6秒

Damon__Li

牛人

newkid

凑合着看吧，时间太久了也没有注释，我自己都看不懂了（悲剧啊！）当时还想到一个改进的思路，忘记写下来现在也想不起来了。下周有空再看看吧。

DECLARE
   TYPE t_num IS TABLE OF NUMBER;
   lv_coins t_num := t_num(1,2,5,10,20,50,100,200);
   lv_limit NUMBER := 1000;  --- 10 dollars
   TYPE t_num2 IS TABLE OF NUMBER INDEX BY PLS_INTEGER;
   lv_cnt   t_num2;
   lv_cnt2  t_num2;
   lv_sum NUMBER ;
   lv_ptr NUMBER;
BEGIN
   lv_cnt(0):=1;
   
   FOR i IN 1..lv_coins.COUNT LOOP
       lv_sum := lv_coins(i);
       lv_cnt2:=lv_cnt;
       WHILE lv_sum<=lv_limit LOOP
             lv_ptr := 0;
             WHILE lv_ptr IS NOT NULL LOOP
                   EXIT WHEN lv_ptr+lv_sum>lv_limit;
                   IF NOT lv_cnt.EXISTS(lv_ptr+lv_sum) THEN
                      lv_cnt(lv_ptr+lv_sum):= lv_cnt2(lv_ptr);
                   ELSE
                      lv_cnt(lv_ptr+lv_sum):= lv_cnt(lv_ptr+lv_sum)+lv_cnt2(lv_ptr);
                   END IF;
                   lv_ptr := lv_cnt2.NEXT(lv_ptr);
             END LOOP;
             lv_sum := lv_sum + lv_coins(i);
       END LOOP;
   END LOOP;
   DBMS_OUTPUT.PUT_LINE(lv_cnt(lv_limit));
END;
/

〇〇

How to simulate DML Operations on XML data using XU (XQuery Update)
How to validate XML data using XSD in Oracle XML DB
How to do XML based data manipulation in SQL and XSLT
How to do table column based data manipulation in SQL and XQuery
How to do character based data manipulation in SQL and XQuery
How to convert an Internet HTML Table to CSV format in SQL
How to transform a RefCursor query resultset into HTML table in SQL
How to convert a RefCursor query resultset to CSV format in SQL
How to transform a CSV file into HTML table in SQL
How to transform a database table dataset into HTML table in SQL
How to convert a table dataset to CSV format in SQL
How to select from an alternative table when the table in the From Clause doesn’t exist in the database
How to find the Longest Common Subsequence (LCS) in SQL
How to solve the Feynman’s Puzzle in SQL
How to find the relationships & connections between people in SQL.