腾讯官方微博出题，半小时写出程序可当初级程序员
某一游戏中有一把武器有1到9个等级，每次升级成功的概率为30%，失败的概率为70%，成功升1级，失败降1级，降到一级不能再降，升到9级不能再升，问1000次内升到9级的概率。 --------------------编程问答-------------------- 做不出来的人 是不是还算不上程序员撒 --------------------编程问答-------------------- 半小时做出来。就可以去腾讯做初级程序员了。。 --------------------编程问答-------------------- 感觉跟概率论的做公交停站次数有些相似，只不过这个会降级，降到1不能降。。。求初级程序员以上的人解答 --------------------编程问答-------------------- 0.3的8次方 乘以 9/1000 对吗。。。 --------------------编程问答-------------------- 30% --------------------编程问答-------------------- 错了，0.3的8次方 乘以 8/1000 --------------------编程问答-------------------- 先算8次就成功的概率。然后再算1000次成功的概率。。 --------------------编程问答-------------------- 组合排列？ --------------------编程问答-------------------- （C(1,496)+C(2,496)+...+C(496,496)）*C(8,1000)*(30%)猜 --------------------编程问答-------------------- 这个不是人做的吧，大家可以做做8次，9次，10次，11次，12次升到9级的概率，做到12次的时候已经很麻烦了。
结果等于8次的概率+9次的概率+10次的概率+11次的概率+。。。+1000次的概率？ --------------------编程问答-------------------- 来现一下丑：
using System;--------------------编程问答-------------------- 再看了一下，上面的程序是算不出结果的，哪怕是理论上～
using System.Collections.Generic;
using System.Text;
namespace Test2
{
class Program
{
public class Item
{
public double Rate;
public int Level;
public Item(double rate, int level)
{
Rate = rate;
Level = level;
}
}
static void Main(string[] args)
{
double Result = 0;
Item item;
List<Item> listItem = new List<Item>(2);
listItem.Add(new Item(0.3, 2));
listItem.Add(new Item(0.7, 1));
for (int i = 0; i < 1000; i++)
{
int count = listItem.Count;
for (int j = 0; j < count;)
{
item = listItem[j];
if (item.Level == 9)
{
Result += item.Rate;
listItem.RemoveAt(j);
count--;
}
else
{
listItem[j] = new Item(item.Rate * 0.3, item.Level + 1);
listItem.Add(new Item(item.Rate * 0.7, item.Level > 1 ? item.Level - 1 : 1));
j++;
}
}
}
Console.Write(Result);
Console.ReadKey();
}
}
}
到后面，List装不下，int会溢出，double精度不够...
看来我是不及格了 --------------------编程问答-------------------- 一个对象Item,属性:等级,升级次数
一个方法,bool update(Item item)
还有什么?把升级的过程写在update中
至于概率,不是程序员的事,是数学家的事 --------------------编程问答-------------------- 一种方法是用模拟，模拟1000个1000次，共100万次，得出的结果应当比较靠谱。
一种方法是用递推，f(n + 1, 9) = f(n, 8) * 0.3
f(n+1,7) = f(n, 8) * 0.7 --------------------编程问答-------------------- 1 不知道。
2 对于不如腾讯的初级程序员这个事实我表示毫无压力。
3 虚心向腾讯的初级程序员请教答案，谢谢。 --------------------编程问答-------------------- 86.5% --------------------编程问答--------------------
好难 --------------------编程问答-------------------- l1=4455
l2=1846
l3=838
l4358
l5=122
l6=49
l7=25
l8=6
l9=2301
乖乖，我做 10000人试验 ， 每人武器升1000 级，如果到 9就 停，到 1000次也停
结果 分布如上表 L9 =2301 也就是 差不多 2301/10000 = 23%
对吗？ --------------------编程问答-------------------- 44180
19054
8027
3376
1474
577
218
53
23041
10人 1000次 分布如上 --------------------编程问答--------------------
class Program
{
static void Main(string[] args)
{
Random r = new Random();
List<int> Eva = new List<int>();
for (int i = 0; i < 9;i++ )
{
Eva.Add(0);
}
for (int j = 0; j < 10000;j++ )
{
LV lv = new LV(9,r);
int tryCount = 1000;
for (int i = 0; i < tryCount; i++)
{
if (lv.Advance() == false)
{
tryCount = i;
break;
}
}
// Console.WriteLine("Lv={0} at TryCount= {1}", lv.CurrentLevel, tryCount);
Eva[lv.CurrentLevel-1] += 1;
}
for (int i = 0; i < 9;i++ )
{
Console.WriteLine(Eva[i]);
}
Console.Read();
}
}
--------------------编程问答-------------------- 做这个的不是程序员。沉浸在这个里边的人不会是普通程序员。
public class LV
{
private int _maxLevel;
private Random _random ;
private int _currentLevel;
public LV(int MaxLevel,Random random){
_maxLevel = MaxLevel;
_random = random;
_currentLevel = 0;
CurrentLevel = 1;
}
public bool Advance(){
if (CurrentLevel==_maxLevel)
{
return false;
}
double thisP= _random.NextDouble();
if (thisP<=0.3)
{
CurrentLevel += 1;
}else{
if (CurrentLevel!=1)
{
CurrentLevel -= 1;
}
}
// Console.WriteLine("{0}\t{1}\t{2}", _advCount, CurrentLevel,thisP);
// Console.WriteLine(("").PadRight(CurrentLevel, '-'));
return true;
}
public int CurrentLevel{
get { return _currentLevel; }
set { _currentLevel = value; }
}
}
他给程序员倒杯水，然后拿出一张纸（号称什么“数字设计说明书”）说明一下人家的游戏中的什么环节需要修改一下数字就行了。 --------------------编程问答--------------------
如果是为了考察编程，这个跟概率其实没有什么大关系。你知道用一个Random.Next数来决定升降级就行了（之前先判断是否已经是9级或者1级）。然后用一个for来循环100000次，最后把整个这个三行的程序再循环10000次，来求得一个平均值。
整个程序的行数，用一个人的脚趾头也数出来了。 --------------------编程问答-------------------- --------------------编程问答-------------------- 要不咱们换个说法吧，算算1000次，升级不到9级的概率，看看这两个哪个更好算啊
然后1减去升级不到9级的概率，就是能升级到的概率了
不要死板，要学会迂回啊 --------------------编程问答--------------------
确实，我一开始的思路就错了。 --------------------编程问答-------------------- 升级到9级有两种情况，
第一种是，成功的次数比失败的多8次（按照一次成功一次失败，等级不变来说的）
第二种是，前边一直失败，后面连续成功8次
第三种是，混合1和2的情况，比较复杂，这个能算出来的话，应该就出结果了吧 --------------------编程问答--------------------
高见，原来还有这样的 --------------------编程问答-------------------- 30%~ --------------------编程问答-------------------- 当然，1000次升级不到9级的概率就比较好算了，
第一种情况，成功-失败<8，（这个是无论如何都不会成功的）
第二种情况，成功-失败=8，（成功504次，失败496次）
第三种情况，成功-失败>8，（这个比较复杂了，欢迎补充） --------------------编程问答-------------------- 可以使用统计的方法，模拟升级1000次，10000次也是比较靠谱的，这样就省去了纯理论的概率计算 --------------------编程问答-------------------- public class Weapon {
private static double probability;
/**
* 目标是武器升到9级 那么成功次数-失败次数必然==8；
* @param x 成功次数
* @param y 失败次数
* 可以有不等式
* {
* x+y <= 1000
* x- y = 8
* x > 0
* y > 0
* }
* 得出 x取值范围为9~504
* 循环x从9~504的概率和 即可得出结果
*/
public static void main(String[] args){
for (int i = 8; i <= 504; i++) {
probability += Math.pow(0.3, i)*Math.pow(0.7,i-8);
}
System.out.println(probability);
}
} --------------------编程问答-------------------- 写错了
* 得出 x取值范围为9~504
* 循环x从9~504的概率和 即可得出结果
应该是8~504
* 得出 x取值范围为8~504
* 循环x从8~504的概率和 即可得出结果 --------------------编程问答-------------------- POW(0.3,8)*(1000/8) --------------------编程问答-------------------- 如果要得出“抛一枚硬币，字朝上的概率”，模拟10000次很可能得出近似的答案，因为路径只有2条（PS:也有倒霉到抛10000次全都是字的）
这里的话，10000次根本不够，因为最终的路径数目是（2的1000次方）级数的，来个（10000乘以2的1000次方）次也许可以。
还有31楼的兄弟的这句“那么成功次数-失败次数必然==8”
我连续失败了900次，再连续成功8次，也能升到9级 --------------------编程问答-------------------- 这道题把他想象成一个二叉数 他的最大层是1000 超1000就失败， 然后构造好了， 就全遍历 你懂的 到9的就加上 就是他的概率和！ --------------------编程问答-------------------- 不如初级程序员啊~~~~ --------------------编程问答-------------------- 什么意思啊？求教育
--------------------编程问答-------------------- 这是数学题啊,概率论,最好用数学方法解决.编程模拟是死板的方法,这里编程的意义只是纯粹的计算数字,有点蛋疼... --------------------编程问答-------------------- m = [ 0.7 0.7 0.0 0.0 0.0 0.0 0.0 0.0 0.0
0.3 0.0 0.7 0.0 0.0 0.0 0.0 0.0 0.0
0.0 0.3 0.0 0.7 0.0 0.0 0.0 0.0 0.0
0.0 0.0 0.3 0.0 0.7 0.0 0.0 0.0 0.0
0.0 0.0 0.0 0.3 0.0 0.7 0.0 0.0 0.0
0.0 0.0 0.0 0.0 0.3 0.0 0.7 0.0 0.0
0.0 0.0 0.0 0.0 0.0 0.3 0.0 0.7 0.0
0.0 0.0 0.0 0.0 0.0 0.0 0.3 0.0 0.0
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.3 0.0 ]
x = [1;0;0;0;0;0;0;0;0]
1-sum(m^1001*x)
ans = 0.22856
--------------------编程问答-------------------- 感觉是分成三份计算
1、1000次中只有1-8次成功率
2、1000次中有9--17次成功率
3、1000次18成功次以上的概率
不过好像答案应该只需要2、3 之和 --------------------编程问答-------------------- // TestTX.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <ctime>
int main(int argc, char* argv[])
{
float fSec = 0;
int intCurRange =1;
//产生随机数
srand(unsigned(time(0)));
while(true)
{
fSec = 0.0;
for(int intTestSum = 1000000;intTestSum>=1;intTestSum--)
{
intCurRange = 1;
for(int intCurCount = 1;intCurCount<=1000;intCurCount++)
{
//每次产生0 - 9的数字，当 0<= X <=2 ,就是30%的成功
//当，3<= X <=9就是失败
int intCurRandomNum = rand() % 10;
bool isSec = false;
if(intCurRandomNum <=2) isSec = true;
if(isSec == true)
{
if(intCurRange<9) intCurRange++;
//判断是否已经成功。
if(intCurRange == 9)
{
break;
}
}
else
{
if(intCurRange>1) intCurRange--;
}
}
if(intCurRange == 9) fSec++;
}
printf("成功概率为：%f \n",(fSec / 1000000));
}
return 0;
}
--------------------编程问答-------------------- 有错啊
思考不过关 --------------------编程问答-------------------- 可以从小的分析起：
1->2的成功概率：0.3
1->2->3的成功概率：
0次失败：
0.3*0.3=0.09
1次失败：
0.7*0.3*0.3+0.3*0.7*0.3*0.3=0.0819
2次失败：
0.7*0.7*0.3*0.3+0.3*0.7*0.3*0.7*0.3*0.3=0.04981
3次失败：
0.7*0.7*0.7*0.3*0.3+0.3*0.7*0.3*0.7*0.3*0.7*0.3*0.3=0.03
总的成功率差不多是0.25
1->2->3->4
0次失败：
0.3*0.3*0.3=0.027
1次失败：
0.7*0.3*0.3*0.3+0.3*0.7*0.3*0.3*0.3*2=0.1323
2次失败：
0.7*0.7*0.3*0.3*0.3+0.3*0.7*0.3*0.7*0.3*0.3*2=0.0396
总的成功率差不多是0.2
1->2->3->4->5
0次失败：
0.3*0.3*0.3*0.3=0.081
1次失败：
0.7*0.3*0.3*0.3*0.3+0.3*0.7*0.3*0.3*0.3*0.3*3=0.022
2次失败：
0.7*0.7*0.3*0.3*0.3*0.3+0.3*0.7*0.3*0.7*0.3*0.3*0.3*0.3*3=0.00035721
总的成功概率差不多是0.113
我们来算
1->2->3->4->5->6->7->8->9
0次失败：
0.3*0.3*0.3*0.3*0.3*0.3*0.3*0.3=0.00006561
1次失败：
0.7*0.3*0.3*0.3*0.3*0.3*0.3*0.3*0.3+0.3*0.7*0.3*0.3*0.3*0.3*0.3*0.3*0.3*0.3*7=0.0001424
总的概率差不多是0.0002
那1000次成功次数就是0次。 --------------------编程问答-------------------- 模拟计算大概的吧
原始数组
一千万个 1
投入到升级函数中1000次
然后结果数组中，看看9有多少
这个结果和真实结果会有点点差距。
--------------------编程问答-------------------- 我想说了我也没达标，
private double total = 0;
private void getGaiLv(int dj,double up,double down,int number)
{
if (number > 10)
{
return;
}
else
{
if (dj == 9)
{
total+=1*up;
}
getGaiLv(dj==9?dj:dj+1, up * 0.3 , down * 0.7,number+1);
getGaiLv(dj == 1 ? dj : dj - 1, up * 0.3, down * 0.7, number + 1);
}
}
这2X递归要执行2的N次方（这里N是10自然可以运算出来），如果是1000的话我这电脑是算不出来的了。。
还有我想说的是如果计算概率是用过rand随即数来判断上还是降的话，那我个人认为有问题。这等于用实际数字去估计一个概率，而不能代表概率本身。这就好比人去抛硬币正反面的概率，去试验10000次的时候肯定不会是0.5，但是我们还是认为它是一个均等的概率0.5。表达可能有欠佳。。。。 --------------------编程问答-------------------- double getGaiLv(int level,int times,double gl)
{
if(level == 9)
return gl;
if(times == 1000)
return 0;
times++;
return getGaiLv(level+1,times,gl*0.3)+getGaiLv(level == 1 ?level:level-1,times,gl*0.7);
} --------------------编程问答--------------------
--------------------编程问答-------------------- 39楼厉害.
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
public class TT {
public static void main(String[] args) {
dengji();
}
public static void dengji(){
double[] a=new double[]{0.3,0.3,0.3,0.7,0.7,0.7,0.7,0.7,0.7,0.7};
int count=0;
int x=1;
for(int i=0;i<1000;i++){
Random r=new Random();
int b=r.nextInt(10);
if(a[b]==0.3){
//到了9级，将x值设置为1，重头再来
if(x==8){
count++;
x=1;
}else{
x++;
}
}else{
if(x==1){
x=1;
}else{
x--;
}
}
}
System.out.println(count);
}
}
0.228556827413
--------------------编程问答--------------------
--------------------编程问答-------------------- 概率+递推解法
import java.util.HashMap;
import java.util.Map;
import java.util.Random;
public class TT {
private static Map<String,String> mapCount=new HashMap<String,String>();
public static void main(String[] args) {
//经过1000次这样的对出现的结果分析
for(int i=0;i<1000;i++){
dengji();
}
//经统计：0.0的概率在0.7-0.8之间
System.out.println("概率为："+mapCount);
//那么升到9级的概率为0.2-0.3之间
}
public static void dengji(){
double[] a=new double[]{0.3,0.3,0.3,0.7,0.7,0.7,0.7,0.7,0.7,0.7};
double count=0;
int x=1;
for(int i=0;i<1000;i++){
Random r=new Random();
int b=r.nextInt(10);
if(a[b]==0.3){
//到了9级，将x值设置为1，重头再来，否则加1
if(x==8){
count++;
x=1;
}else{
x++;
}
}else{
//如果随机数是0.7，则表示失败,如果当前数是1，则不变，否则减1
if(x==1){
x=1;
}else{
x--;
}
}
}
count=count/1000;
if(mapCount.get(count+"")==null){
mapCount.put(count+"",1+"");
}else{
mapCount.put(count+"",(Integer.parseInt(mapCount.get(count+""))+1)+"");
}
}
}
设 p[i][j] 表示第i次升级后，达到j级的概率。比如p[0][1] = 1(初始级别为1级), p[1][2] = 0.3.计算出p[i][j]后，对p[9][j] (0 < j < 1000)进行累加即可.
p[i][j]的值可以通过前一次升级的概率值(p[i-1][j-1], p[i-1][j], p[i-1][j+1])来递推得到.所以可以得到
p[i][j]的递推公式:
当1 < j < 9时: p[i][j] = p[i-1][j-1] * 0.3 + p[i-1][j+1] * 0.7
当j == 9时: p[i][j] = (p[i-1][j] + p[i-1][j-1]) * 0.3
当j == 1时: p[i][j] = (p[i-1][j] + p[i-1][j+1') * 0.7
然后有初始条件p[0][1] = 1, p[0][j] = 0 (j > 0)(第0次为1级的概率为1)。
下面是代码:
#include<iostream>
using namespace std;
int const MAX_TIMES = 1000;
int const MAX_LEVEL = 9;
double per[MAX_TIMES + 1][MAX_LEVEL + 1];
int main()
{
for(int i = 1;i <= MAX_LEVEL;++i)
per[0][i] = 0;
per[0][1] = 1; // 初始化
for(int i = 1;i <= MAX_TIMES;++i)
{
for(int j = 1; j<= MAX_LEVEL; ++j)
{
if(j == MAX_LEVEL)
{
per[i][j] = (per[i - 1][j] + per[i - 1][j - 1])* 0.3;
} else if(j == 1)
{
per[i][j] = (per[i - 1][j] + per[i - 1][j + 1])* 0.7;
} else
{
per[i][j] = per[i - 1][j - 1] * 0.3 + per[i - 1][j + 1] * 0.7;
}
}
}
double ans = 0;
for(int i = 0;i <= MAX_TIMES;++i)
ans += per[i][9];
cout << per[1][2] << endl;
cout << ans << endl;
return 0;
}
--------------------编程问答-------------------- 相比39L，我写得好像略显复杂。结果0.228557
#include <stdio.h>--------------------编程问答--------------------
#define TIMES 1000
#define LEVELS 9
#define SUCCESS_RATE 0.3
#define FAIL_RATE (1 - SUCCESS_RATE)
void upgrade(double *first, int levels) {
double *p, *last, old, new;
last = first + levels - 1;
p = first;
while (p <= last) {
if (p == first)
new = (*p) * FAIL_RATE;
else
new = old * SUCCESS_RATE;
if (p < last - 1)
new += *(p + 1) * FAIL_RATE;
else if (p == last)
new += *p;
old = *p;
*p = new;
++p;
}
}
int main() {
int i;
double p[LEVELS];
p[0] = 1;
for (i = 0; i ！= TIMES; ++i)
upgrade(p, LEVELS);
printf("%f", *(p + LEVELS - 1));
}
你这个相当于：
m = [ 0.7 0.7 0.0 0.0 0.0 0.0 0.0 0.0 0.0
0.3 0.0 0.7 0.0 0.0 0.0 0.0 0.0 0.0
0.0 0.3 0.0 0.7 0.0 0.0 0.0 0.0 0.0
0.0 0.0 0.3 0.0 0.7 0.0 0.0 0.0 0.0
0.0 0.0 0.0 0.3 0.0 0.7 0.0 0.0 0.0
0.0 0.0 0.0 0.0 0.3 0.0 0.7 0.0 0.0
0.0 0.0 0.0 0.0 0.0 0.3 0.0 0.7 0.0
0.0 0.0 0.0 0.0 0.0 0.0 0.3 0.0 0.0
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.3 1.0 ]
x = [1;0;0;0;0;0;0;0;0]
n = m^1000*x
n(9)
ans = 0.228556827413034
--------------------编程问答--------------------
// 初始化概率，各数组索引就是对应的等级，第1级的概率就是values[0]的值，第9级就是values[8]
decimal[] values = new decimal[] { 1, 0, 0, 0, 0, 0, 0, 0, 0 };
decimal up = 0.3m, down = 0.7m;
//开始循环
for (int i = 0; i <= 1000; i++)
{
//初始化新数组来存放概率变动后的结果
decimal[] temp = new decimal[] { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
for (int j = 0; j < temp.Length; j++)
{
//第1级时
if (j == 0)
{
temp[j] += values[j] * down;
}
else
{
temp[j - 1] += values[j] * down;
}
//第9级时
if (j == temp.Length - 1)
{
temp[j] += values[j] * up;
}
else
{
temp[j + 1] += values[j] * up;
}
}
values = temp;
//输出，每循环100次输出一次
if (i % 100 == 0)
{
Console.WriteLine("第{0}次", i);
//for (int j = 0; j < 9; j++)
//{
// Console.WriteLine("第{0}级概率:\t{1}", j + 1, temp[j]);
//}
//这里为了输出结果简短所以只输出了三级概率
//输出第1级的概率
Console.WriteLine("第{0}级概率:\t{1}", 1, temp[0]);
//输出第5级的概率
Console.WriteLine("第{0}级概率:\t{1}", 4, temp[4]);
//输出第9级的概率
Console.WriteLine("第{0}级概率:\t{1}", 8, temp[8]);
Console.WriteLine();
}
}
运行结果：
第0次
第1级概率: 0.7
第4级概率: 0.0
第8级概率: 0.0
第100次
第1级概率: 0.5717074437909508263443388030
第4级概率: 0.0192870834829091589927628518
第8级概率: 0.0006506672847176283763127033
第200次
第1级概率: 0.5717074292102149898391197790
第4级概率: 0.0192870894485724146137502391
第8级概率: 0.0006506681571569517050194432
第300次
第1级概率: 0.5717074292102102438647503688
第4级概率: 0.0192870894485743564145781347
第8级概率: 0.0006506681571572356807205720
第400次
第1级概率: 0.5717074292102102438632055724
第4级概率: 0.0192870894485743564152101836
第8级概率: 0.0006506681571572356808130048
第500次
第1级概率: 0.5717074292102102438632055724
第4级概率: 0.0192870894485743564152101836
第8级概率: 0.0006506681571572356808130048
第600次
第1级概率: 0.5717074292102102438632055724
第4级概率: 0.0192870894485743564152101836
第8级概率: 0.0006506681571572356808130048
第700次
第1级概率: 0.5717074292102102438632055724
第4级概率: 0.0192870894485743564152101836
第8级概率: 0.0006506681571572356808130048
第800次
第1级概率: 0.5717074292102102438632055724
第4级概率: 0.0192870894485743564152101836
第8级概率: 0.0006506681571572356808130048
第900次
第1级概率: 0.5717074292102102438632055724
第4级概率: 0.0192870894485743564152101836
第8级概率: 0.0006506681571572356808130048
第1000次
第1级概率: 0.5717074292102102438632055724
第4级概率: 0.0192870894485743564152101836
第8级概率: 0.0006506681571572356808130048
可以看到第一级的概率始终在半数以上，而第九级才万分之6.5
100次之后概率变化已经很小了，而400次之后已经无法用28位小数来精确表征概率变化了 --------------------编程问答--------------------
高手，那个 我的 18 楼相当啥？ 代码 在20楼， 19楼 为10万人
能把 39楼的解释一下吗？ --------------------编程问答-------------------- 俺在一家小公司里面，用不了这些东西！ --------------------编程问答--------------------
你那个相当于蒙特卡罗。
http://en.wikipedia.org/wiki/Markov_chain#Finite_state_space --------------------编程问答--------------------
你没有考虑：升到第9级就完成任务，不会再降到第8级。 --------------------编程问答--------------------
这就是所说的知足常乐吧
--------------------编程问答-------------------- 能否换一种方式，正为0.3，负为-0.7,10000位全排列后计算和为9，注意开始为1，和始终大于等于1并且小于等于9。当然实际上是无法解除的。
这个题的事件不是独立的，也不是完全的条件概率，个人感觉基本无解！ --------------------编程问答-------------------- 有解，递推的可以. --------------------编程问答-------------------- 刚开始为一级的话，大约为0.3，这是个二次分布，但如果直接算太复杂，但可以用中心极限定理模拟。 --------------------编程问答-------------------- --------------------编程问答-------------------- #include<stdio.h>
#include<stdlib.h>
#define try_time 1002
#define level 12
int main()
{
double ans=0;
double dp[try_time][level];
for(int i=0;i<level;i++)
for(int j=0;j<try_time;j++)
dp[j][i]=0;
//for(int i=1;i<=1000;i++)dp[i][0]=1;
dp[0][1]=1;
for(int i=1;i<1001;i++)
for(int j=1;j<10;j++){
if(j==1){
dp[i][j]+=dp[i-1][j+1]*0.7;
dp[i][j]+=dp[i-1][j]*0.7;
}else if(j==9){
dp[i][j]+=dp[i-1][j-1]*0.3;
}else if(j==8){
dp[i][j]+=dp[i-1][j-1]*0.3;
}
else{
dp[i][j]+=dp[i-1][j-1]*0.3;
dp[i][j]+=dp[i-1][j+1]*0.7;
}
}
for(int i=1;i<=1000;i++)ans+=dp[i][9];
printf("%lf\n",ans);
return 0;
} --------------------编程问答-------------------- 我是新手，用vb写的程序，采用递归法，时间复杂度O(n),代码如下:
Public Class Form1
Const up = 0.3, down = 0.7
Dim n As Integer
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
n = n + 1
Dim p(8), m(8) As Double
p(0) = 1
For i = 1 To 8
p(i) = 0
Next
For l = 1 To n
For i = 0 To 8
m(i) = p(i)
Next
For i = 1 To 6
p(i) = m(i - 1) * up + m(i + 1) * down
Next
p(7) = m(6) * up
p(0) = m(1) * down + m(0) * down
p(8) = m(7) * up + m(8)
Next
Label1.Text = p(8)
End Sub
End Class
n表示要求升级次数（本题中要求为1000次），当n=1000时，计算结果为0.2285568274
当n=10000时，计算结果为0.92744996，当n=100000时，计算结果接近1. --------------------编程问答-------------------- 可以转化成带权有向图，计算起点到终端的概率。 --------------------编程问答-------------------- 乱弹无责任分析：理想情况下前后两次升级的成功率或失败率没有必然关联。
如果10次达到9级，s + f = 10, s - f = 8, s = 9，f = 1，此时的失败次数只允许1次，概率0.7；反之成功率0.3。
如果100次到达9级，先按照10为单位划分100次为10个区间，如此只允许其中一个区间是-1（失败），概率0.7，成功率0.3；每个子区间10次，如果该区间为-1区间，则概率为0.7，成功率0.3。
如果1000次，三级分解为100x10，10x10，10x1，任意级别的失败概率都是0.7，成功率0.3。 --------------------编程问答-------------------- 强化次数越多几率越高这是毫无疑问的 --------------------编程问答-------------------- 无解。。。 --------------------编程问答-------------------- 这是齐次有限马尔科夫链，属于生灭过程，建个转移方程，然后求1000次幂就行了。 --------------------编程问答-------------------- 首先想到的是动态规划。设 f(m, n) 为进行了 m 次之后恰好为 n 级的概率，则有递推关系：
f(m, n) = f(m-1, n-1) * 0.3 + f(m-1, n+1) * 0.7
即上次到 n-1 级然后升级，或者上次到 n+1 级然后降级。
但是当 n = 1 或者 n = 9 时，上面的式子不适用，有边界条件：
f(m, 1) = f(m-1, 1) * 0.7 + f(m-1, 2) * 0.7 // 即 1 级的时候降级仍为 1 级
f(m, 8) = f(m-1, 7) * 0.3 // 因为 8 级不能从 9 级降级得到，这个还是看了陈硕大牛前面的评论才得到的
f(m, 9) = f(m-1, 8) * 0.3
代码：
#include <stdio.h>
double ar[1001][10];
int main(int argc, char *argv[])
{
int i;
for (i = 0; i <= 9; i++) {
ar[1][i] = 0;
}
ar[1][1] = 0.7;
ar[1][2] = 0.3;
ar[2][1] = 0.7;
int j;
for (i = 2; i <= 1000; i++) {
ar[i][1] = ar[i-1][1] * 0.7 + ar[i-1][2] * 0.7;
for (j = 2; j <= 7; j++) {
ar[i][j] = ar[i-1][j-1] * 0.3 + ar[i-1][j+1] * 0.7;
}
ar[i][8] = ar[i-1][7] * 0.3;
ar[i][9] = ar[i-1][8] * 0.3;
}
double ans = 0.0;
for (i = 1; i <= 1000; i++) {
ans += ar[i][9];
}
printf("%f\n", ans);
return 0;
}
结果：0.228557 --------------------编程问答-------------------- 这道题90%只是数学问题，只有10%可能还不到的部分是在考跟程序相关的东西 --------------------编程问答-------------------- 这个是要靠运气的啦 哈哈 --------------------编程问答--------------------
请问这个式子是什么意思？ --------------------编程问答--------------------
java.... --------------------编程问答--------------------
妙，很不错。。 --------------------编程问答-------------------- 一看到这样的东西
我就马上想到的是递归
程序员的编程实现时间不重要，关键是思维.
思维错误，再快也是白搭。 --------------------编程问答--------------------
其他看不懂 就这个最简单 而且易于理解啊 动态规划还是要好好看看 --------------------编程问答-------------------- 高中生路过 惭愧不懂得编程 看到这题很有意思 想了个特笨的办法【捂面】望大神们指点
P=0.3^8*(0C992*0.7^992+2C992*0.3^2*0.7^990+4C992*0.3^4*0.7^988…+988C992*0.3^988*0.7^4+990C992*0.3^990*0.7^2+992C992*0.3^992)
这、这种方程式可以用什么编程软件算出来么…？【抱头】 --------------------编程问答--------------------
表示看不懂这个式子。
不过上面都是模拟了1000次升级，硬算出来的。没啥神奇的地方。
以1为总概率开始算，算出每一级的概率。
第一次升级，1级是0.7，2级是0.3
以后第n级的概率 = n-1级 * 0.3 + n+1级 * 0.7
不过要注意第1级和第9级。 --------------------编程问答--------------------
不好意思 是马尔科夫 有限状态空间
不是蒙特卡罗吧。。。 --------------------编程问答-------------------- C就是数学排列组合问题常用的rCn=比如从n个球里不放回取出r个球且不重复的取法总数。
1000次升级里从一升到九，极限情况需要“1->2->3->4->5->6->7->8”升八次就成，所以是 0.3^8
剩下1000-8=992次需要达到升降抵消的平衡状态才能保证上述“极限情况”不被破坏。
抵消，即为N升N降，为偶数次，所以只看偶数情况。
0C992*(0.3^0)*(0.7^992) 【992中0升992降】|||- -b|||绝对咒怨
2C992*(0.3^2)*(0.7^990) 【992中2升990降】
4C992*(0.3^4)*(0.7^988) 【992中4升988降】
6C992*(0.3^6)*(0.7^986) 【992中6升986降】
...
986C992*(0.3^986)*(0.7^6) 【992中986升6降】
988C992*(0.3^988)*(0.7^4) 【992中988升4降】
990C992*(0.3^990)*(0.7^2) 【992中990升2降】
992C992*(0.3^992)*(0.7^0) 【992中992升0降】|||- -Y|||圣光护佑
全加起来，再乘以0.3^8就得这坑爹的方程式了...
应、应该是这样没错吧...【忐忑
--------------------编程问答--------------------
你回帖不看帖，我回答了 54 楼的两个问题。
18 楼 startstartsvip 的做法是蒙特卡罗。
39楼的解释 是马尔科夫 --------------------编程问答-------------------- 数量问题 --------------------编程问答-------------------- 好吧！看见这个题就没做的欲望。。。 --------------------编程问答-------------------- 这个题简单 ３０％ ＊ ３０ ％ ＊．．．(504次)*70%*70%(496次) --------------------编程问答--------------------
如果次数没有上限，极限情况下的成功概率应该是越接近0.3，而失败的概率也是越接近0.7。
但成功率是[0,0.3]区间渐渐增加，失败率则是[1.0,0.7]区间渐渐减少。 --------------------编程问答-------------------- 这个要吃10快钱以上盒饭的程序员去做，我这5块钱盒饭的 就不参合了 --------------------编程问答--------------------
这样一说那我就不知道该说出题者不严谨还是我理解不够，当然我自己更倾向于前者，自以为还是答上来了的，好歹初级程序员咱还是够得上滴
不过，惭愧的是，虽然程序写出来了，不过在下只是基于高中生物里特性遗传的概率规律做出来的，没有上面那么多高等数学的概念和人物 --------------------编程问答-------------------- 0.3的八次方，就这样吧，别被自己绕进去了。 --------------------编程问答-------------------- 建议，写入一个正常关闭的标志位 --------------------编程问答-------------------- 0.3的八次方 --------------------编程问答-------------------- 0.3的八次方 我觉得是 八次 就成功升到9及的概率
理论上说省多少次必定会成功呢？我觉得是(1除以0.3的八次方)即（1/0.3^8）=15241.579027587258039932937052279
1000次 那么理论上说就是 大约是15241次
1000(次)/ (1/0.3^8)=
0.065610000000000000000000000000037
概率似乎是 6.561%
不知道 这个概率对不对 --------------------编程问答-------------------- 我觉得是先算 八次 就会成功升到9及的概率
理论上说省多少次必定会成功呢？
我觉得是(1除以0.3的八次方)即（1/0.3^8）=15241.579027587258039932937052279
1000次 那么理论上说就是 大约是15241次
1000(次)/ (1/0.3^8)=
0.065610000000000000000000000000037
概率似乎是 6.561%
不知道 这个概率对不对 --------------------编程问答-------------------- 至于降级 我没有考虑这是我的错...
如果考虑了...
那么这个概率 有点 不可想象... --------------------编程问答-------------------- 你们都想多了 这不是程序题 他是数学题 你们仔细想想 自己高数的时候 是不是都学过概率 回去翻翻书 这题不难的 --------------------编程问答-------------------- 所以就会出什么保护药什么的 让玩家砸钱进去，然后TX就从中牟利;
要进TX，先要学会这些 --------------------编程问答-------------------- 模拟的结果是0.23
public class UpgradeSimulator {
private final static double UP_RATE = 0.7;
public static void main(String[] args) {
int success = 0;
int failed = 0;
for (int i = 0; i < 100000; i++) {
if (simulate()) {
success++;
}
else {
failed++;
}
}
System.out.println("Rate: " + ((double) success / (success + failed)));
}
public static boolean simulate() {
int curlevel = 1;
for (int i = 0; i < 1000; i++) {
if (Math.random() >= UP_RATE) {
curlevel++;
if (curlevel == 9) return true;
}
else {
if (curlevel > 1) curlevel--;
continue;
}
}
return false;
}
} --------------------编程问答--------------------
--------------------编程问答-------------------- 如下图，红线右面的交点是升到9级的，左面的交点是升不到9级的。图只做到升21次，写个程序自己补全1000次吧。。。
public class UpgradeSimulator {
private final static double UP_RATE = 0.7;
public static void main(String[] args) {
int success = 0;
int failed = 0;
for (int i = 0; i < 100000; i++) {
if (simulate()) {
success++;
}
else {
failed++;
}
}
System.out.println("Rate: " + ((double) success / (success + failed)));
}
public static boolean simulate() {
int curlevel = 1;
for (int i = 0; i < 1000; i++) {
if (Math.random() >= UP_RATE) {
curlevel++;
if (curlevel == 9) return true;
}
else {
if (curlevel > 1) curlevel--;
continue;
}
}
return false;
}
}
--------------------编程问答-------------------- 有没有不用计算机纯手工算出来的，我想到都是要用程序的
补充：.NET技术 , C#
