題目

骰子的點數是1 到 6，當有n個骰子的時候，其點數和等于m的數量

如當n = 4 m = 23時候 有下面四種：

5666
6566
6656
6665

解題

深度優先，開始第一感覺很復雜，然后就沒有寫，后來在最后幾分鐘寫了出來，但是提交發現以為有相同的情況，用TreeSet存放符合條件的種類，發現還是不對，剛在本地測試發現下面的問題

當求 2 個數的和是 6的時候，輸出結果是 15 、24、33、42、51、6，當兩個數的和是5的時候輸出：14、41、23、32、5 ，是這種情況我誤以為是由于出現重復數據，最后時間不對，也沒有再改

但是對于自己能做到這里還是比較滿意的。

對于出現長度不到n，和等于m的情況，只有利用其長度了。應該有其他的好方法

import java.util.Iterator; import java.util.TreeSet; import java.util.Scanner; public class Main{static int count;static TreeSet<String> set;public static void main(String[] args){Scanner in = new Scanner(System.in);while(in.hasNext()){count = 0;set = new TreeSet<String>();int n = in.nextInt();int m = in.nextInt();String s = "";dfs(n,n,m,s);System.out.println(count+"\t"+set.size());Iterator it = set.iterator();while(it.hasNext()){String tmp = (String)it.next();System.out.print(tmp+"\t");}}in.close();}public static void dfs(int N,int n,int m,String s){if(n<0)return;if(n==0 && m==0 && s.length() == N){//System.out.println(s); set.add(s);count++;return;}while((n--)>0){for(int i =1;i<=6;i++){s+=i+"";dfs( N,n,m-i,s);s = s.substring(0,s.length()-1);}}} }

那么少的程序，傻子都能寫出來了。。。

提交的程序少了一行：

s = s.substring(0,s.length()-1);

這樣對個數竟然沒有影響（雖然可能輸出只有一個數就等于m的情況）

原因是判斷少了

s.length() == N

但是為什么不加判斷是否等于N時候為什么可以輸出一個數的和等于m的情況？可能是while循環中用到了 n--的情況

我的這個方法還是不好，用N判斷長度，太冗余，利用TreeSet增加了空間復雜度。

上面可以發現我定義count最后的值和TreeSet的大小是一樣的，所有可以不用TreeSet。

更新如下

import java.util.Scanner; public class Main{static int count;public static void main(String[] args){Scanner in = new Scanner(System.in);while(in.hasNext()){count = 0;int n = in.nextInt();int m = in.nextInt();String s = "";dfs(n,n,m,s);System.out.println(count);}in.close();}public static void dfs(int N,int n,int m,String s){if(n<0)return;if(n==0 && m==0&& s.length() == N){count++;return;}while((n--)>0){for(int i =1;i<=6;i++){s+=i+"";dfs( N,n,m-i,s);s = s.substring(0,s.length()-1);}}} }

在第一次寫的時候也沒有TreeSet 在輸入2 6多出一個結果的時候才用TreeSet，結果還是沒有找到主要問題，但是網易測試用例要自己輸入，一個坑，不知道自己的用例是否太少。

?

測出結果

1 6 1 1 6 2 6 5 5 15 24 33 42 51 4 23 4 4 5666 6566 6656 6665 5 25 126 126 16666 25666 26566 26656 26665 34666 35566 35656 35665 36466 36556 36565 36646 36655 36664 43666 44566 44656 44665 45466 45556 45565 45646 45655 45664 46366 46456 46465 46546 46555 46564 46636 46645 46654 46663 52666 53566 53656 53665 54466 54556 54565 54646 54655 54664 55366 55456 55465 55546 55555 55564 55636 55645 55654 55663 56266 56356 56365 56446 56455 56464 56536 56545 56554 56563 56626 56635 56644 56653 56662 61666 62566 62656 62665 63466 63556 63565 63646 63655 63664 64366 64456 64465 64546 64555 64564 64636 64645 64654 64663 65266 65356 65365 65446 65455 65464 65536 65545 65554 65563 65626 65635 65644 65653 65662 66166 66256 66265 66346 66355 66364 66436 66445 66454 66463 66526 66535 66544 66553 66562 66616 66625 66634 66643 66652 66661

?2016-03-22?22:27:18

上面程序有問題

參加下面

public ArrayList<String> nSumk(int n,int k){String list = "";ArrayList<String> result = new ArrayList<String>();if(n<=0 || k< n || k > n*6 ) // 非法輸入return result;DFS(n,1,k,result,list);return result;}public void DFS(int n,int start,int k,ArrayList<String> result,String list){if(list.length() == n && k==0){result.add(new String(list));return;}for(int j=1;j<=6;j++){if(k-j<0)return;k -=j;list += j;DFS(n,start+1,k,result,list );k +=j;list = list.substring(0,list.length() - 1); // DFS(n,start+1,k-j,result,list + j); }}

?

總結

以上是生活随笔為你收集整理的2016网易实习生编程题：n个骰子的和等于m的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。