C程序设计基础LAB11

由
内容纲要

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;
}

留下评论