首页 > 试题广场 >

大富翁游戏

[编程题]大富翁游戏
  • 热度指数:9432 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
大富翁游戏,玩家根据骰子的点数决定走的步数,即骰子点数为1时可以走一步,点数为2时可以走两步,点数为n时可以走n步。求玩家走到第n步(n<=骰子最大点数且是方法的唯一入参)时,总共有多少种投骰子的方法。

输入描述:
输入包括一个整数n,(1 ≤ n ≤ 6)


输出描述:
输出一个整数,表示投骰子的方法
示例1

输入

6

输出

32
/*思路:
递推关系为:dp[i] = dp[i - 1] * 2, dp[i]为走到第n步投骰子的方法
例如,dp[3] = 4
1 1 1
2 1
1 2
3
那么求解dp[4]:
方案一:dp[4]和dp[3]投骰子的次数一致,那么只需要在最后一次的投掷点数上加1,前提是n <= 骰子最大点数
1 1 1 -> 1 1 (1 + 1) = 1 1 2
2 1 -> 2 (1 + 1) = 2 2
1 2 -> 1 (2 + 1) = 1 3
3 -> (3 + 1) = 4
方案二:dp[4]比dp[3]多投掷一次
1 1 1 -> 1 1 1 1
2 1 -> 2 1 1
1 2 -> 1 2 1
3 -> 3 1
因此,dp[4] = dp[3] * 2 
*/
#include <iostream>
using namespace std;
int kinds(int n)
{
 int dp[n + 1];
 dp[1] = 1;
 for(int i = 2; i <= n; i++)
  dp[i] = dp[i - 1] << 1;
 return dp[n]; 
}
int main()
{
 int N;
 cin>>N;
 cout<<kinds(N)<<endl;
}
编辑于 2017-07-13 11:30:51 回复(1)
归纳:f(n) = f(n-1)+f(n-2)+f(n-3)+....+f(1)+1,f(1)=1,f(2)=2.则f(n)=2^(n-1).

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n;
while(cin>>n){
cout<<pow(2,n-1)<<endl;
}
return0;
}
编辑于 2017-07-23 19:42:11 回复(4)
我很机智的用手算的,反正就6个输入...

importjava.util.Scanner; 
publicclassMain { 
    publicstaticvoidmain(String[] args) { 
        Scanner in = newScanner(System.in); 
        intn=in.nextInt();
        Main d=newMain();
        d.myMethod(n);
           
    } 
     
    publicvoidmyMethod(intn)
    {
        switch(n)
        {
        case1:
            System.out.println("1");
            break;
        case2:
            System.out.println("2");
            break;
        case3:
            System.out.println("4");
            break;
        case4:
            System.out.println("8");
            break;
        case5:
            System.out.println("16");
            break;
            default:
                System.out.println("32");
                 
        }
    }
}
发表于 2017-08-30 21:40:52 回复(15)
思路:设f(n)表示到第n步时总共有f(n)种投骰子的方法,那么到第n-1步时总共有f(n-1)种投骰子的方法;那么到第n-2步时总共有f(n-2)种投骰子的方法......
规律: 从第n-1步到第n步,只有一种可能性(投骰子结果为 1 ),所以从第n-1步到第n步共有f(n-1)*1 种投骰子的方法;  从第n-2步到第n步,只有一种可能性(投骰子结果为 2 ),所以从第n-2步到第n步共有f(n-2)*1 种投骰子的方法;
从第n-3步到第n步,只有一种可能性(投骰子结果为 3 ),所以从第n-3步到第n步共有f(n-3)*1 种投骰子的方法;
依次类推:f(n) = f(n-1)+f(n-2)+f(n-3)+....+f(1)+f(0),且f(1)=f(0)=1;  
代码:
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        System.out.println(getSum(n));
    }
    public static int getSum(int n){
       int count=0;
        if(n==1)
            count=1;//f(1) =1
        else if(n==2)
            count=2;//f(2)=2
        else{
            for(int i=1;i<n;i++){
                count+=getSum(n-i);//计算f(n) = f(n-1)+f(n-2)+f(n-3)+....+f(1)
            }
            count=count+1;//再加f(0) = 1
        }
        return count;
    }
}

发表于 2017-07-14 14:14:03 回复(11)
//用dp[i]表示走到i步的种树,递推公式为dp[i] = dp[i - 1] + dp[i - 2] + ......dp[i - 6]
//分别表示i-1步再走一步,i-2步再走2步...i-6步再走6步的情况。
import java.util.*;

/**
 * Created by 梅晨 on 2017/8/20.
 */

public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int num = in.nextInt();
            System.out.println(dep(num));
        }
    }

    public static int dep(int num){
        int[] dp = new int[num + 1];
        dp[0] = 1;
        for(int i = 1; i <= num; i++){
            for(int j = 1; j <= 6; j++){
                if(i >= j){
                    dp[i] += dp[i - j];
                }
            }
        }
        return dp[num];
    }
}

发表于 2017-09-09 01:09:18 回复(0)
为啥没人注意(1 ≤ n ≤ 6)这个条件
发表于 2017-07-25 16:31:20 回复(0)
//2^n
#include<iostream>
#include<cmath>
using namespace std;
 
 
intmain(){
    intn;
    cin>>n;
    inttimes=1;
    intt=n-1;
    times=times<<t;
 
    cout<<times;
    return0;
}
发表于 2017-06-27 11:20:21 回复(0)
把n拆成1和n-1,然后就可以使用递归。当然,也可以把这个递归方程解出来得到通项为2^(n-1)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strN;
        while((strN = br.readLine()) != null){
            int n = Integer.parseInt(strN);
            System.out.println(solve(n));
        }
    }
    
    private static int solve(int n) {
        if(n == 1) return 1;
        return 2 * solve(n - 1);     // 乘以2是因为对称,可以是最后走的一步,也可以是刚开始走的一步
    }
}


发表于 2020-10-16 16:01:40 回复(0)
#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int*Num = new int[n+1];
    Num[1]=1;
    for(inti=2; i<=n; ++i)
        Num[i]=2*Num[i-1];
    cout<<Num[n];
    return 0;
}

发表于 2018-06-12 22:34:54 回复(0)
###递归调用f(此次)=f(上次)*2,且每增加一步,方法是前一种状态的两倍。两倍怎么来的呢
###(3,2)两步走变为三步就是(3,2,1)和(1,3,2 ##############################
def f(nn):
    if nn == 1:
        return 1    
    else:
        m = f(nn-1)*2
        return m
n=input()
n=int(n)
print(f(n))
###32


编辑于 2018-04-08 22:52:32 回复(0)
var n = readline();
var r = dice(n);
print(r);
function dice (n) {
    if(n == 0) {
        return1;
    }
    var result = 0;
    for(var i = 0; i <= n - 1; i++) {
        result += dice(i);
    };
 
    returnresult;
}

编辑于 2017-09-04 16:06:28 回复(0)
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin>>n;
    vector<int> dp(n+1,0);
    dp[0] = 1;
    for(int i = 1 ; i <= n ; i++) {
        for(int j = 1 ; j <= i ; j++) {
            dp[i] += dp[i-j];
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}
编辑于 2017-08-28 14:48:17 回复(0)
// 2的幂的规律
#include<cstdio>
#include<iostream>
using namespace std;
int main(){ 
    int n;
    while(cin>>n){
        printf("%d\n",1<<(n-1));
   }
 return 0;
}

编辑于 2017-08-24 11:45:53 回复(1)
采用递归:
int NumOfMethods(int n)
{
if(n==1)
return 1;
return (NumOfMethods(n-1)<<1);
}//代码简洁,但是会有重复计算,需要开辟内存存放中间结果,如:
int NumOfMethods(int n)
{
if(n<1 || n>6)
return 0;
int *result=new int[n+1];
result[0]=1;result[1]=1;

for(int i=2;i<=n;i++)
{
result[i]=result[i-1]<<1;
}
return result[n];
delete result;//动态申请事务内存需要手动释放
}//能够直接利用之前的计算结果(当然,空间换取时间性能)

编辑于 2017-07-10 15:50:24 回复(0)
还是那个公式:f(n) = f(n-1) + f(n-2) + .... + f(1) + f(n-n).
这个f(n-n)是指:投的骰子数正好是n本身,那么f(0) = 1.
从公式上,我们能看出来,用递归做法比较简单.
在公式等号后的每一个函数,依然可以单独分解,例如 : f(n-1) = f(n-2) + ....+ f(1) + f(0),所以当n存在时,那么我们要分解n次(循环n次).
#!_*_coding:utf-8_*_
def numer(n):
    sum = 0 #用于记录每次分解得到的步数
    if n == 1 or n == 0:
        return 1
    else:
        for i in range(n):# 根据当前n的值,循环n次,将其分解为f(0) + f(1) + ... + f(n-1)
            sum += numer(i)
        return sum # 返回当前n进行的步数

编辑于 2018-04-19 10:42:01 回复(1)
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n=1<<(sc.nextInt()-1);
        
        System.out.println(n);
    }
}
发表于 2021-09-09 10:00:17 回复(0)
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        final int i = sc.nextInt();
        final int[] ints = new int[i];
        ints[0] = 1;
        for (int j = 1; j < ints.length; j++) {
            for (int k = 0; k < j; k++) {
                ints[j] += ints[k];
            }
            ints[j]++;
        }
        System.out.println(ints[i-1]);
    }
}


编辑于 2021-02-18 10:10:03 回复(0)
我把它看成一个列出整数划分之后再全排列数数的问题,这个思路可以吗?
有没有人能够做出来,我列不出来
发表于 2020-08-12 12:28:40 回复(0)
#include<iostream>
#include<string.h>
using namespace std;

int main() {
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    int row = s1.size();
    int col = s2.size();
    int dp[row][col];
    memset(dp, 0, sizeof(dp));
    int len = 0;
    for (int i = 0; i < row; i++) {
        dp[i][0] = s1[i] == s2[0] ? 1 : 0;
        len = max(len, dp[i][0]);
    }
    for (int j = 0; j < col; j++) {
        dp[0][j] = s1[0] == s2[j] ? 1 : 0;
        len = max(len, dp[0][j]);
    }
    for (int i = 1; i < row; i++) {
        for (int j = 1; j < col; j++) {
            if (s1[i] == s2[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                len = max(len, dp[i][j]);
            }
        }
    }
    cout<<len;
}


发表于 2020-08-01 17:41:06 回复(0)

美团2017 JAVA

[编程题]大富翁游戏
[编程题]拼凑钱币
[编程题]最大矩形面积
[编程题]最长公共连续子串

这道题限制了,降低了问题难度,我首先想到的是插板法。
总共走n步,最多分n次走。这个问题就相当于把n个小球分隔为~份,也就是n-1的空隙的插板问题。插1个板就是,插2个板就是,所有情况加和就是
当我非常得意地把代码都写出来突然感觉有点不对劲,这TM不就是的二项式展开吗?淦!
然后我又自己写了一个求2的幂的函数,实际上也可以直接用Math.pow()。

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Main s=new Main();
        int a=(new Scanner(System.in)).nextInt();
        System.out.print(new Double( Math.pow(2,n-1)).intValue());
    }
    //求2^a
    int t(int a){
        int ans=1;
        while(--a>0){
            ans*=2;
        }
        return ans;
    }
    //求题解
    int p(int a){
        int ans=0;
        for (int i=0;i<a;i++){
            ans+=c(i,a-1);
        }
        return ans;
    }
    //求b选择a的可能性
    int c(int a,int b){
        return x(b)/(x(b-a)*x(a));
    }
    //求阶乘a!
    int x(int a){
        if (a==1||a==0) return 1;
        return a*x(a-1);
    }
}
发表于 2020-04-19 17:41:59 回复(0)