每日归档： 2022年10月29日

void find_number()
{
    int array[15] =
    {
        2, 3, 5, 7, 11,
        13, 17, 19, 23, 29,
        31, 37, 41, 43, 47
    };
 
    int left = 0, right = 15-1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (array[mid] < 29)
            left = mid + 1;     // 繼續搜尋剩下的右半段
        else if (array[mid] > 29)
            right = mid - 1;    // 繼續搜尋剩下的左半段
        else if (array[mid] == 29)
        {
            // 找到了其中一個數字
            cout << mid << ':' << array[mid];
            return;
        }
    }
 
    cout << "找不到29";
}

 

void reverse(char* s)
{
    int n = strlen(s);
    for (int i=0; i<n/2; i++)
        swap(s[i], s[n-1-i]);
}

 

void string_searching()
{
    char text[14] = "It's a pencil.";
    char pattern[6] = "a pen";
 
    // 仔細估量枚舉範圍
    for (int i=0; i<14-6+1; i++)
    {
        bool find = true;
        for (int j=0; j<5; j++)
            if (text[i+j] != pattern[j])
            {
                find = false;
                break;
            }
 
        if (find)
            cout << "短字串出現在第" << i << "個字元";
    }
}

 

struct Point {float x, y;};
 
// 計算兩點之間的距離
float dist(Point a, Point b)
{
    float dx = a.x - b.x;
    float dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}
 
void closest_pair()
{
    Point point[10] =
    {
        {3, 3}, {1, 5}, {4, 6}, {2, 8}, {9, 9},
        {2, 1}, {7, 2}, {6, 5}, {9, 4}, {5, 9}
    };
 
    float d = 1e9; 
    for (int i=0; i<10; i++) 
        for (int j=i+1; j<10; j++)
            // 記錄最短的距離
            d = min(d, dist(point[i], point[j]));
 
    cout << "距離是" << d;
}

 

方法1：

int sum_of_cubes(int n)
{
    int sum = 0;
    for (int i=1; i<=n; i++)
        sum += i * i * i;
    return sum;
}
 
void print_sum_of_cubes()
{
    int n;
    while (cin >> n && n > 0)
        cout << sum_of_cubes(n);
}

方法2：

int sum_of_cubes(int n)
{
    // 其值為 0 表示沒有存入答案
    static int answer[10 + 1] = {};
 
    // 如果已經計算過，就直接讀取表格的答案。
    if (answer[n] != 0) return answer[n];
 
    // 如果不曾計算過，就計算一遍，儲存答案。
    int sum = 0;
    for (int i=1; i<=n; i++)
        sum += i * i * i;
    return answer[n] = sum;
}
 
void print_sum_of_cubes()
{
    int n;
    while (cin >> n && n > 0)
        cout << sum_of_cubes(n);
}

方法3：

void print_sum_of_cubes()
{
    // 預先建立立方數表格
    int cube[10 + 1];
    for (int i=1; i<=10; i++)
        cube[i] = i * i * i;
 
    int n;
    while (cin >> n && n > 0)
    {
        // 直接讀取表格的立方數
        int sum = 0;
        for (int i=1; i<=n; i++)
            sum += cube[i];
        cout << sum;
    }
}

方法4：

int sum_of_cubes(int n)
{
    int sum = 0;
    for (int i=1; i<=n; i++)
        sum += i * i * i;
    return sum;
}
 
void print_sum_of_cubes()
{
    // 預先計算所有答案
    int answer[10 + 1];
    for (int i=1; i<=10; i++)
        answer[i] = sum_of_cubes(i);
 
    // 直接讀取表格的答案
    int n;
    while (cin >> n && n > 0)
        cout << answer[n];
}

方法5：

void print_sum_of_cubes()
{
    // 預先計算答案，寫死在程式碼裡面。
    int answer[10 + 1] =
    {
        0, 1, 9, 36, 100, 225,
        441, 784, 1296, 2025, 3025
    };
 
    // 直接讀取表格的答案
    int n;
    while (cin >> n && n > 0)
        cout << answer[n];
}

 

void counting_sort()
{
    int array[5] = {3, 6, 9, 9, 1}; //对5个数进行排序，用i表示
    int c[ 9 + 1 ] = {};            //数字范围是0~9，用j表示
    
    for (int i = 0; i < 5; i++){  //统计数字数量
        c[array[i]]++; 
    }

    for (int j = 0, i = 0; j < 10 && i < 5; j++){ //从小到大读取lookup table，并排序
        while (c[j] > 0){
            c[j]--;
            array[i++] = j; 
        }
    }
}

 

#include <iostream>

using namespace std;

void count_letter_frequency()
{
    char s[101] = {};
    int c[26] = {};
    
    cin >> s; 

    for (int i = 0; s[i]; i++){
        if (s[i] >= 'A' && s[i] <= 'Z'){
            s[i] = s[i] - 'A' + 'a';
        }
    }

    for  (int i = 0; s[i]; i++) {
        if (s[i] >= 'a' && s[i] <= 'z'){
            c[s[i] - 'a'] ++;
        }
    }

    for (int i = 0; i < 26; i++){
        cout << (char) ('a' + i) << ':' << c[i] << endl;
    } 

    
}

void count_letter()
{
    char s[15] = "Hello World!";
 
    // 字母統一換成小寫
    for (int i=0; s[i]; i++)
        if (s[i] >= 'A' && s[i] <= 'Z')
            s[i] = s[i] - 'A' + 'a';
 
    // 枚舉26種英文字母
    for (int i=0; i<26; i++)
    {
        // 枚舉字串的所有字元
        int c = 0;
        for (int j=0; s[j]; j++)
            if (s[j] == 'a' + i)
                c++;
 
        // 印出一種字母的數量
        cout << (char)('a' + i) << ':' << c;
    }
}

 

#include <vector>
#include <algorithm>
using namespace std;
struct Guest {int arrival, leave;} g[10];

bool cmp(int i, int j){
    return abs(i) < abs(j);
}


void maximum_guest()
{
    vector<int> time;
    for (int i = 0; i < 10; i++){
        time.push_back(+g[i].arrival);
        time.push_back(-g[i].leave);
    }

    sort(time.begin(), time.end(), cmp);
    int n = 0, maximum = 0;

    for (int i = 0; i < time.size(); i++){
        if (time[i] >= 0) n++ ;
        else n --;
    }

    maximum = max(maximum, n);
    cout << maximum << endl;
}

 

Above Average

It is said that 90% of frosh expect to be above average in their class. You are to provide a reality check.

The first line of standard input contains an integer C, the number of test cases. C data sets follow. Each data set begins with an integer, N, the number of people in the class (1 <= N <= 1000). N integers follow, separated by spaces or newlines, each giving the final grade (an integer between 0 and 100) of a student in the class. For each case you are to output a line giving the percentage of students whose grade is above average, rounded to 3 decimal places.

Sample Input

5
5 50 50 70 80 100
7 100 95 90 80 70 60 50
3 70 90 80
3 70 90 81
9 100 99 98 97 96 95 94 93 91

Output for Sample Input

40.000%
57.143%
33.333%
66.667%
55.556%

#include <stdio.h>
#include <iostream>

using namespace std;

int main()
{
    int testcase, length;
    cin >> testcase;
    while (testcase--){
        cin >> length;
        double sum = 0;
        double *scores = new double[length];
        int count = 0;

        for (int i = 0; i < length; i++){
            cin >> scores[i];
            sum += scores[i];
        }

        double avg = sum / length;

        for (int i = 0; i < length; i++){
            if (scores[i] > avg){
                count ++;
            }
        printf(".3f%%\n", count * 100.0 / length);
        }
    }
}

 

题目：不断的输入整数，输出中值，如果中间有两个数，输出他们平均值的整数部分。

分析：简单题。因为数据不大，每次输入数据后，排序即可。

#include <stdio.h>
#include <iostream>
#include <stdlib.h>

using namespace std;

int main()
{
    int n, count = 0;
    long data[10005];
    while ( ~scanf("%d", &n) ){
        data[count ++] = n;
        sort(data, data + count);
        if ( count & 1) // 等价于 count % 2 == 1;
        {
            printf("%ld", data[count / 2]);
        } else{
            printf("%ld", (data[count / 2] + data[count / 2 - 1]) /2 );
        }
        return 0; 
    }
}