分类： OJ算法刷题

#include <stdio.h>
#include <iostream>
using namespace std;

int main()
{
    int col, row;
    char c;
    scanf("%d %c", &col, &c);
    if (col % 2 == 1){
        row = col / 2 + 1;
    } else {
        row = col / 2;
    }

    for (int i = 0; i < col; i++){
        putchar(c);
    }
    putchar('\n');

    for (int i = 0; i < row - 2; i++){
        putchar(c);
        for (int k = 0; k < col - 2; k++){
            putchar(' ');
        }
        putchar(c);
        putchar('\n');
    }
    for (int i =0; i < col;i++){
        putchar(c);
    }
    return 0;
}

 

#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    int maxn = 210;
    int n, a[maxn];
    while (cin >> n){
        for (int i=0; i<n; i++){
            scanf("%d", &a[i]);
        } 
        int x,k;
        cin >> x;
        for ( k = 0; k < n; k++){
            if (a[k] == x)
                cout << k;
        }

        if ( k == n ){
            cout << -1;
        }
    }
}

 

include <iostream>
using namespace std;

const int maxn = 100010;
int school[maxn] = {0};

int main()
{
    int n, schID, score;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> schID >> score;
        school[schID] += score;
    }

    int k, MAX = -1;
    for (int i = 1; i<= n; i++){
        if(school[i] > MAX){
            max = school[i];
            k = i;
        }
    }

    cout << k << ' ' << MAX;
    return 0;
}

 

#include <iostream>
using namespace std;

int main(void)
{
    int n, step = 0;
    cin >> n;
    while(n != 1){
        if ( n % 2 == 0 ){
            n /= 2;
        } else {
            n = ( 3 * n + 1 ) / 2)
        }
        step++;
    }
    cout << step;
}

 

int gcd1(int a, int b)
{
    // 令 a 比 b 大，比較容易思考。
    while (b != 0)
    {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int gcd2(int a, int b)
{
    // 令 a 比 b 大，比較容易思考。
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

 

我們知道要怎麼確定一個整數是不是 9 的倍數－如果它每位數的總和是9的倍數，那它就是9的倍數。這種檢驗的方法其實是一種遞迴的方法，而且我們把這種方法遞迴的深度稱作 N 的 9-degree 。

你的工作就是，給你一個正整數N，判斷他是不是9的倍數，而且如果他是9的倍數你還需要判斷它的 9-degree。

Input 

輸入含有多組測試資料。每組測試資料一列包含一個正數 N。

當 N=0 時代表輸入結束；輸入的數最大可以到1000位數。

Output 

對於每一組測試資料，請輸出它是否是 9 的倍數及它的 9-degree。輸出格式請參考Sample Output。

Sample Input 

999999999999999999999
9
9999999999999999999999999999998
837
0

Sample Output 

999999999999999999999 is a multiple of 9 and has 9-degree 3.
9 is a multiple of 9 and has 9-degree 1.
9999999999999999999999999999998 is not a multiple of 9.
837 is a multiple of 9 and has 9-degree 2.

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

int main()
{
    string s;
    while(cin >> s){
        if (s.length() == 0 || s[0] == '0'){
            break; 
        }

        int sum = 0;
        for (int i = 0; i < s.length(); i++){
            sum += s[i] - '0'; //先把所有位加起来
        }

        int dep = 0;
        int is9mul = 0;

        if (sum % 9 == 0){
            is9mul = 1; //如果一个数是9的倍数，肯定能一直递归下去
            dep = 1; //开始的时候，只要能被9整除，深度就是1;
        }

        while (sum % 9 == 0 && sum > 9){
            int temp = sum;
            sum = 0;
            while(temp){
                sum += temp % 10; 
                temp /= 10;
            }
            dep++;
        }
        cout << s << " is ";
        if (!is9mul) cout << "not ";
        cout << "a multiple of 9";
        if (dep) cout << " and has 9-degree " << dep;
        cout << "." << endl;
    }
    return 0;
}

 

在這個問題中，給你2個整數N，M。請你找出^NP_M（在N個東西種找出M個東西排列不同的方式）最後一個不為0的數字。例如：¹⁰P₃=10*9*8=720，所以答案為2。

Input

每筆測試資料一列。每列有2個整數 N（0 <= N <= 20000000）,M（0 <= M <= N）。

Output

對每一列輸入，請輸出^NP_M最後一個不為0的數字。

Sample Input

10 10
10 5
25 6

Sample Output

8
4
2

#include <iostream>
using namespace std;

long long P(long long n, long long m)
{
    long long ans=1;
    for (long long i = n - m + 1; i<=n; i++){
        ans *= i; 
    }
    
    return ans;
}

long long calc(long long p)
{
    if (p % 10 == 0)
        return calc(p / 10);
    else
        return p % 10;
}

int main()
{
    long long n, m, p;
        while(cin >> n >> m){
        if (n < m) continue;
        p = P(n, m);
        //cout << p << endl;
        cout << calc(p) << endl;
    }
}

 

Step１:
任选一个正整数Ａ作为这个数列的第一项。
Step２:
如果Ａ＝１则停止。
Step３:
如果Ａ为偶数，则Ａ＝Ａ／２然后重新回到Step２。
Step４:
如果Ａ为奇数，则Ａ＝３*Ａ＋１然后重新回到Step２。
这个演算法已经被证明当首项小于等于109时这个数列最终都会在Step２停止，但是有些Ａ值在这个数列中会超出许多电脑的整数上限。在这个问题中我们想​​要计算这个数列的长度，而数列的终止有两种情况：1.最终会在Step２停止或是2.某一项会在Step４超出一个特定的上限。

Input

输入包含许多组待测资料，每一列代表一组待测资料，每组待测资料包含两个正整数，第一个数为首项Ａ，第二个数为这个数列的上限Ｌ，无论Ａ或Ｌ都不会大于2,147,483,647（32位元有号整数的最大值），且首项Ａ总是小于上限Ｌ。当输入为两个负数时代表输入结束。

Output

 

对每组待测资料必须输出它为第几组（从１开始），一个冒号，首项Ａ的值，上限Ｌ的值，以及此一数列的项数。

#include<stdio.h>
int main()
{long n,m,i,A,t=1;
while(scanf("%ld%ld",&n,&m)!=EOF){
    A=n;
    if(n<0&&m<0)    break;
    if(n==1)        break;
    for(i=0;;){
        if(n%2==0)  {n/=2;i++;}
        else        {n=(3*n+1);i++;}
        if(n>m)     break;
        if(n==1)    {i++;break;}
    }
    printf("Case %ld: A = %ld, limit = %ld, number of terms = %ld\n",t,A,m,i);
    t++;
}
return 0;
}

 

考慮以下的演算法：

1.         輸入 n
2.         印出 n
3.         如果 n = 1 結束
4.         如果 n 是奇數 那麼 n=3*n+1
5.         否則 n=n/2
6.         GOTO 2

例如輸入 22, 得到的數列： 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

據推測此演算法對任何整數而言會終止 (當列印出 1 的時候)。雖然此演算法很簡單，但以上的推測是否真實卻無法知道。然而對所有的n ( 0 < n < 1,000,000 )來說，以上的推測已經被驗證是正確的。

給一個輸入 n ,透過以上的演算法我們可以得到一個數列（1作為結尾）。此數列的長度稱為n的cycle-length。上面提到的例子, 22 的 cycle length為 16.

問題來了：對任2個整數i，j我們想要知道介於i，j（包含i，j）之間的數所產生的數列中最大的 cycle length 是多少。

Input

輸入可能包含了好幾列測試資料，每一列有一對整數資料 i，j 。

0< i，j < 1,000,000

Output

對每一對輸入 i , j 你應該要輸出  i, j 和介於 i, j 之間的數所產生的數列中最大的 cycle length。

#include <stdio.h>

int cycle_length(int n)
{
    int length = 1;
    while (n!=1) {
        if (n % 2 == 1){
            n = 3 * n + 1;
        } else {
            n /= 2;
        }
        length++;
    }
    return length;
}

int main()
{
    int n, i, j ,k , max, oi, oj;
    while (scanf("%d %d",&i, &j) == 2){
        oi = i; oj = j;
        max = 0;
        if (i > j){
            k = i;
            i = j;
            j = k;
        }

        for (n = i; n <= j; n++){
            k = cycle_length(n);
            if (k > max) max = k;
        }
        printf("%d %d %d\n", oi, oj, max);
    }
}

 

#include <stdio.h>
#include <iostream>
using namespace std;

int string_length(char *s)
{
    int n = 0;
    while (s[n]) n++;
    return n;
}

int pow10(int exp)
{
    int n = 1;
    for (int i = 0; i < exp; i++)
        n *= 10;
    return n;
}

void string_to_integer()
{
    char s[10] = "26962869";
    int length =string_length(s);
    
    int n = 0;
    for (int i = 0; i < length; i++)
        n += (s[i] - '0') * pow10(length - 1 - i);

    cout << n;
}

void string_to_integer2()
{
    char s[10] = "26962869";

    int n = 0;
    for (int i = 0; s[i]; i++)
        n = n * 10 + s[i] - '0';

    cout << n;
}