分类： OJ算法刷题

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

 

有n個整數的序列我們稱為jolly jumper，如果相鄰的2個數其差的絕對值恰好為1到n-1。

例如：1 4 2 3 就是jolly jumper（n=4）。因為相鄰2數的差的絕對值為3,2,1，就是1到n-1。

但是 1 4 2 -1 6 不是jolly jumper（n=5）。因為相鄰2數的差的絕對值為3,2,3,7，並非1到n-1。

你的任務是寫一個程式來判斷一個整數序列是否為jolly jumper。

Input

每組測試資料一列，第一個正整數為 n（n <= 3000），代表此整數序列的長度。接下來有n個整數，代表此整數序列。請參考Sample Input。

Output

對每一組測試資料，輸出此整數序列是否為jolly jumper。請參考Sample Output。

Sample Input

4 1 4 2 3
5 1 4 2 -1 6

Sample Output

Jolly
Not jolly

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

int main(void)
{
    int n;
    while (~scanf("%d", &n)){
        int array[3001] = {};
        int str[3001] = {};

        for (int i = 0; i < n; i++)
            scanf("%d", &array[i]);

        for (int i = 0; i < n - 1; i++)
            str[abs(array[i] - array[i+1])] = true;

        int count = 1;
        for (int i = 1; i <= n - 1; i++)
            if (str[i]) count ++;

        if (count == n - 1) printf("Jolly\n");
        else printf("Not jolly\n");
    }
}

 

题目大意：
给你振幅和频率，让你画出波形。
如：

3
2

波形为：

1
22
333
22
1

1
22
333
22
1

#include <iostream>
using namespace std;
void print(int a, int b);

int main()
{
    int n, leap, a, b;
    cin >> n;
    leap = 0;
    
    while(n--){
        if (leap != 0)
        //    cout << "CR"<<endl;
        cout << endl;

        leap++;
        cin >> a >> b;
        print(a, b);
    }
}

//a为振幅，b为频率
void print(int a, int b)
{
    for (int i = 0; i < b; i++){ //一共打印b个波浪

        for (int j = 1; j < a; j++){   //打印波峰之前
            for (int k = 1; k <= j; k++){  //打印每行
                cout << j;
            }
            cout << endl;
    }


        for (int j = 1; j <= a; j++){ //打印波峰
            cout << a;
        }

        for (int j = a - 1; j >= 1; j--){ //打印波峰之后
            for (int k = 1; k <= j; k++ ){ //打印每行
                cout << j;
            }
            cout << endl;
        }
        if(i != b - 1)
        //    cout << "LF" << endl;
        cout << endl;
    }
}

 

#include <iostream>
using namespace std;

void print_line ( int n)
{
    for (int i = 1; i <= n; i++){
        cout << '@' ;
    }
        cout <<  endl;
}

void print_triangle(int n)
{
    for (int i = n; i >= 1; i--){
        print_line(i);
    }
}