PAT《数据结构学习与实验指导》实验项目集 2-05 2-06 2-07 2-08

题目地址：here

没什么可说的，大水题

 1 #include<cstdio>
 2 #include<cmath>
 3 int main()
 4 {
 5     int n;
 6     scanf("%d", &n);
 7     int data[n];
 8     double average = 0.0;
 9     for(int i = 0; i < n; i++)
10     {
11         scanf("%d", &data[i]);
12         average += data[i];
13     }
14     average /= n;
15     double variance = 0.0;
16     for(int i = 0; i < n; i++)
17     {
18         variance += (average - data[i])*(average - data[i]);
19     }
20     variance = sqrt(variance/n);
21     printf("%.5f", variance);
22     return 0;
23 }

pat 2-06 数列求和

从结果的最后一位开始计算，依次计算每一个十进制位，水题

 1 #include<cstdio>
 2 #include<stack>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int num,times;
 8     scanf("%d%d", &num, &times);
 9     if(times == 0)printf("0");
10     else
11     {
12         //从结果的最后一位开始计算，结果放入栈中
13         stack<char> result;
14         int carryBit = 0;//进位
15         for(int i = times; i >=1 ;i--)
16         {
17             int tmp = num*i + carryBit;
18             result.push(tmp%10 + '0');
19             carryBit = tmp/10;
20         }
21         if(carryBit != 0)
22             printf("%d", carryBit);
23         while(result.empty() == false)
24         {
25             printf("%c", result.top());
26             result.pop();
27         }
28     }
29     return 0;
30 }

pat 2-07 素因子分解

这是整数的素因子分解问题，一个整数n的素数因子不可能同时大于sqrt(n), 先用“埃拉托斯特尼筛法”计算出sqrt(n)以内的所有素数，然后再注逐一查看这些素数是否是n的素因子，要注意最后除完所有素因子后如果结果>1,这个数也是素因子

 1 //筛选法寻找n以内的素数，返回素数的个数
 2 int findPrime(const int n, int prime[])
 3 {
 4     int primeNum = 0;
 5     bool isPrime[n+1];//0表示是素数，1表示非素数
 6     memset(isPrime, 0, sizeof(isPrime));
 7     for(int i = 2; i <= n; i++)
 8         if(isPrime[i] == 0)
 9         {//所有素数的倍数都不是素数
10             prime[primeNum++] = i;
11             for(int k = 2, t; (t = i*k)<= n; k++)
12                 isPrime[t] = 1;
13         }
14     return primeNum;
15 }
16 int main()
17 {
18     long N;
19     scanf("%ld", &N);
20     int *prime = new int[(int)sqrt(N)];
21     int primeNum = findPrime(sqrt(N), prime);
22     printf("%d=", N);
23     if(N == 1)printf("1");
24     bool isFirst = true;
25     for(int i = 0; i < primeNum; i++)
26     {
27         int exp = 0;
28         while(N % prime[i] == 0)
29         {
30             exp++;
31             N = N / prime[i];
32         }
33         if(exp != 0)
34         {
35             if(isFirst == false)
36                 printf("*");
37             else isFirst = false;
38             printf("%d", prime[i]);
39             if(exp > 1)
40                 printf("^%d", exp);
41         }
42     }
43 
44     if(N > 1)
45     {
46         if(isFirst == false)
47             printf("*");
48         printf("%d", N);
49     }
50     return 0;
51 
52 }

pat 2-08 用扑克牌计算24点

24点游戏请参考我的博客：here

注意的是结果后面要加‘ ’,要不然会提示答案格式错误

#include<cstdio>
#include<iostream>
#include<string>
using namespace std;

//cards[i]的值是通过表达式expr[i]计算而来
bool GameRecur(double cards[], string expr[],
               const int cardsNum, const int result)
{
    if(cardsNum == 1)
    {
        if(cards[0] == result)
        {
            //cout<<expr[0]<<endl;
            return true;
        }
        else return false;
    }
    //从已有数中任选两个,计算得到中间结果，并且和剩余的数一起存在cards数组的前
    //cardsNum-1个位置
    for(int i = 0; i<cardsNum; i++)
    {
        for(int k  = i+1; k < cardsNum; k++)
        {
            double a = cards[i], b = cards[k];
            cards[k] = cards[cardsNum-1];
            string expra = expr[i], exprb = expr[k];
            expr[k] = expr[cardsNum-1];

            cards[i] = a + b;
            expr[i] = '(' + expra + '+' + exprb + ')';
            if(GameRecur(cards, expr, cardsNum-1, result))
                return true;

            cards[i] = a - b;
            expr[i] = '(' + expra + '-' + exprb + ')';
            if(GameRecur(cards, expr, cardsNum-1, result))
                return true;

            if(a != b)
            {
                cards[i] = b - a;
                expr[i] = '(' + exprb + '-' + expra + ')';
                if(GameRecur(cards, expr, cardsNum-1, result))
                    return true;
            }

            cards[i] = a * b;
            expr[i] = '(' + expra + '*' + exprb + ')';
            if(GameRecur(cards, expr, cardsNum-1, result))
                return true;

            if(b != 0)
            {
                cards[i] = a / b;
                expr[i] = '(' + expra + '/' + exprb + ')';
                if(GameRecur(cards, expr, cardsNum-1, result))
                    return true;
            }

            if(a != 0 && a!= b)
            {
                cards[i] = b / a;
                expr[i] = '(' + exprb + '/' + expra + ')';
                if(GameRecur(cards, expr, cardsNum-1, result))
                    return true;
            }

            //把选出来的两个数放回原位
            cards[i] = a;
            cards[k] = b;
            expr[i] = expra;
            expr[k] = exprb;
        }
    }
    return false;
}

string PointGame(int cards[], const int cardsNum, const int result)
{
    string expr[cardsNum];
    double cardsCopy[cardsNum];
    for(int i = 0; i < cardsNum; i++)
    {
        char buf[30];
        sprintf(buf, "%d", cards[i]);
        expr[i] = buf;
        cardsCopy[i] = cards[i];
    }
    if(GameRecur(cardsCopy, expr, cardsNum, result))
        return expr[0].substr(1, expr[0].length()-2); //去掉最外层的括号
    else return "-1";
}

int main()
{
    int a[4];
    for(int i = 0; i < 4; i++)
        scanf("%d", &a[i]);
    printf("%s
", PointGame(a,4,24).c_str());
    return 0;
}