1048. 骰子点数之和问题
//********** Specification of Combination **********
double probability(int n, int k);
/* Precondition: n和k为整数
Postcondition: 返回n个骰子同时扔后点数之和为k的概率
*/
double probability(int n, int k) { //TODO: your function definition
}
#include <stdio.h>
int main() {
int n, k;
scanf("%d%d", &n, &k);
printf("%.6f\n", probability(n, k));
return 0;
}
骰子六面为1,2,3,4,5,6.
题解
本题的数据范围给得很明显了,前7个点的n只有10以内,后3个点则最多可能有n=2000的情况。因此首先排除递归,暴力递归深搜肯定最多只能过前7个点。后三个点计算次数是a^n数量级的,想想看a^2000是什么概念。
那么这题只能通过一些数学技巧来解决了。
首先,已知第一个骰子,有6种情况,总和分别为1,2,3,4,5,6;
那么,不妨设一个二维数组a[n+1][k+1],其中,n为骰子个数,k为总和的值,数组元素为此种情况出现的概率;
由此,已知的条件可以写为a[1][1]=1/6, a[1][2]=1/6, ... , a[1][6]=1/6;
试着算一下a[2][1],很明显,两个骰子不可能骰出总和为1的情况,因此我们需要在开始就排除这些情况;
算一下a[2][2],是1/6/6=1/36;
a[2][3],是1/6/6(a[1][1])+1/6/6(a[1][2])=1/18;
然后考虑a[n][k],用你聪明的小脑瓜想一想,很轻松可以归纳出来一个递推公式:
a[n][k] = a[n-1][k-1]/6 +...+a[n-1][k-6]/6;
然后就好做了,开个超大数组,从1个骰子为基础,逐个求出所有的情况,返回a[n][k]就是最终答案了。
代码
double probability(int n, int k);
double probability(int n, int k){
int x, y;
double dp[2001][12011];
if(k > n*6 || k < n) return 0;
for(int i=1; i<7; i++) dp[1][i]=1.0/6.0;
for(int i=2; i<=n; i++){
for(int j=i; j<=6*i; j++){
dp[i][j]=0;
if(j >= i+5) {dp[i][j]+=dp[i-1][j-6]/6.0;}
if(j >= i+4) {dp[i][j]+=dp[i-1][j-5]/6.0;}
if(j >= i+3) {dp[i][j]+=dp[i-1][j-4]/6.0;}
if(j >= i+2) {dp[i][j]+=dp[i-1][j-3]/6.0;}
if(j >= i+1) {dp[i][j]+=dp[i-1][j-2]/6.0;}
dp[i][j] += dp[i-1][j-1]/6.0;
}
}
return dp[n][k];
}
#include <stdio.h>
int main(){
int n, k;
scanf("%d%d", &n, &k);
printf("%.6f\n", probability(n, k));
return 0;
}
思考一下
这题还有更好的做法,可以省去不少空间,想想怎么省?
或许还有更快的方法,但我没想到,欢迎各路大佬指点。
1049. 最长单词
定义函数 LongestWord 找出一个字符串中最左边的最长单词。
单词之间用一个空格或多个空格分隔。
/***************************************************************/
/* */
/* DON'T MODIFY main function ANYWAY! */
/* */
/***************************************************************/
#include <stdio.h>
//********** Specification of LongestWord **********
void LongestWord(const char str[],char result[])
/* PreCondition:
str is a string with length no more than 80
PostCondition:
find the first longest word in str, and put it in result.
changing str is not allowed
*/
{ //TODO: your function definition
}
/***************************************************************/
#define N 80
int main()
{ char s[N+1],r[N+1];
gets(s);
//********** LongestWord is called here ************
LongestWord(s,r);
//**************************************************
printf("%s\n",r);
return 0;
}
题解
我不知道这题凭啥是medium难度,建议改成naive。
考虑一下找最大值的方法,定义一个max等于数组第一个元素,然后遍历数组,碰到比它大的就复制给它,遍历结束后max里存放的就是数组元素的最大值。
那么这题也是一样的做法,只不过我们需要用到三个标记,单词起始位置,单词结束位置,最长单词长度。
碰到空格,或者结束符,意味着读完一个单词。如果再优化一些,可以碰到结束符就跳出循环。
读完单词后,得到目前单词的长度,和最长单词的长度比一比,如果比它长,那么就将新的起始下标,结束下标以及单词长度赋值给旧的三个标记。
代码
#include <stdio.h>
void LongestWord(const char str[],char result[]){
int start = 0;
int end = 0;
int lastCount = -1;
for(int i = 0; i < 81; i++){
if(str[i]=='\0')
break;
int count = 0;
int temp = i;
while(str[i] != ' ' && str[i] != '\0'){
count++;
i++;
}
if(lastCount<count){
start = temp;
end = i;
lastCount = count;
}
}
for(int i = 0; i<=end-start; i++)
result[i] = str[i+start];
}
/***************************************************************/
#define N 80
int main()
{ char s[N+1],r[N+1];
gets(s);
//********** LongestWord is called here ************
LongestWord(s,r);
//**************************************************
printf("%s\n",r);
return 0;
}
1050. 矩阵转置
/***************************************************************/
/* */
/* DON'T MODIFY main function ANYWAY! */
/* */
/***************************************************************/
#define N 10
/********** Specification of transpose **********/
void transpose(int (*m)[N], int n)
/* PreCondition:
m is the address of a matrix and n(n<=N) is a positive integer
PostCondition:
m is transposed
*/
{
/*TODO: your function definition*/
}
/***************************************************************/
#include <stdio.h>
int main()
{
int m[N][N], i, j, n;
scanf("%d", &n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &m[i][j]);
/********** transpose is called here **************/
transpose(m, n);
/**************************************************/
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
printf("%d%c", m[i][j], j < n - 1 ? ' ' : '\n');
return 0;
}
题解
首先得知道转置是啥,其实就是矩阵的行变列,列变行。
其实就是交换a[i][j]和a[j][i]。
有一个小问题,如果直接遍历,每个元素其实会被交换两次,等于没交换,所以开一个新的矩阵,两个矩阵来回倒腾就行了。、
代码
#include<malloc.h>
#define N 10
/********** Specification of transpose **********/
void Transpose(void *a, int n)
/* PreCondition:
a is beginning address of a square matrix, n is the number of rows for the matrix, no more than 80.
PostCondition:
the matrix is transposed
*/
{
int* c = (int*)a;
int *b = (int*)malloc(n*n*sizeof(int));
for(int i = 0; i < n;i++){
for(int j = 0; j < n;j++)
*(b+i*n+j) = *(c+j*n+i);
}
for(int i = 0; i < n;i++){
for(int j = 0; j < n;j++)
*(c+i*n+j) = *(b+i*n+j);
}
}
/***************************************************************/
#include <stdio.h>
#include <stdlib.h>
int main()
{ int *a,n,i; scanf("%d",&n);
a=(int*)malloc(n*n*sizeof(int));
for (i=0;i<n*n;i++) scanf("%d",a+i);
Transpose(a,n);
for (i=0;i<n*n;i++)
{ printf("%d ",a[i]); if ((i+1)%n==0) printf("\n"); }
free(a);
return 0;
}