CUMTOJ数据结构练习1

数据结构 C++ 数据结构

发布时间 : 2019-10-22 17:12

阅读 :

问题 A: 回文数

题目描述

我们把从左往右和从右往左念起来相同的数字叫做回文数。例如，75457就是一个回文数。
当然某个数用某个进制表示不是回文数，但是用别的进制表示可能就是回文数。
例如，17是用十进制表示的数，显然它不是一个回文数，但是将17用二进制表示出来是10001，显然在二进制下它是一个回文数。
现在给你一个用十进制表示的数，请你判断它在2到16进制下是否是回文数。

输入

输入包含多组测试数据。每组输入一个用十进制表示的正整数n（0 < n < 50000），当n = 0时，输入结束。

输出

对于每组输入，如果n在216进制中的某些进制表示下是回文数，则输出“Number i is palindrom in basis ”，在后面接着输出那些进制。其中i用n的值代替，后面输出的进制中，每两个数字之间空一个。
如果n在216进制的表示下都不为回文数，则输出“Number i is not a palindrom”，其中i用n的值代替。

样例输入

17
19
0

样例输出

Number 17 is palindrom in basis 2 4 16
Number 19 is not a palindrom

思路

代码

#include <iostream>
using namespace std;
int main()
{
    int Judge(int n, int i);
    int Decimal_Num = 1;
    while(Decimal_Num)
    {
        cin >> Decimal_Num;
        if(Decimal_Num == 0)
            return 0;
        int arr[20] = { 0 };
        int i, t = 0;
        for(i = 2; i <= 16; i++)
        {
            if(Judge(Decimal_Num, i))
            {
                t = 1;
                arr[i] = 1;
            }
        }
        if(t)
        {
            cout << "Number " << Decimal_Num << " is palindrom in basis ";
            for(i = 2; i <= 16; i++)
            {
                if(arr[i])
                    cout << i << " ";
            }
            cout << endl;
        }
        else
            cout << "Number " << Decimal_Num << " is not a palindrom\n";
    }
    return 0;
}
int Judge(int n, int i)
{
    int a[50];
    int g, num = 0;
    while(n)
    {
        a[num++] = n % i;
        n /= i;
    }
    int t = 1;
    for(g = 0; g < num / 2; g++)
    {
        if(a[g] != a[num - 1 - g])
        {
            t = 0;
            break;
        }
    }
    return t;
}

问题 C: 单词排序

题目描述

小红学会了很多英文单词，妈妈为了帮小红加强记忆，拿出纸、笔，把 N 个单词写在纸上的一行里，小红看了几秒钟后，将这张纸扣在桌子上。妈妈问小红：“你能否将这 N 个单词按照字典排列的顺序，从小到大写出来？”小红按照妈妈的要求写出了答案。现在请你编写程序帮助妈妈检查小红的答案是否正确。注意：所有单词都由小写字母组成，单词两两之间用一个空格分隔。

输入

输入包含两行。
第一行仅包括一个正整数N(0<N≤26)。
第二行包含N个单词，表示妈妈写出的单词，两两之间用一个空格分隔。
单个单词长度不超过1010。

输出

输出仅有一行。针对妈妈写出的单词，按照字典排列的顺序从小到大排列成一行的结果，每个单词后带一个空格。

样例输入

4
city boy tree student

样例输出

boy city student tree

思路

代码

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
    string word[30];
    int word_num, i;
    cin >> word_num;
    for (i = 0; i < word_num; i++)
        cin >> word[i];
    sort(word, word + word_num);
    for (i = 0; i < word_num; i++)
    {
        if (i == 0)
            cout << word[i];
        else
            cout << " " << word[i];
    }
    cout << endl;
    return 0;
}

问题 D: 4.5.17 Power Strings

题目描述

Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then ab = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (the empty string) and a^(n+1) = a*(a^n).

输入

Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

输出

For each s you should print the largest n such that s = a^n for some string a.

样例输入

abcd
aaaa
ababab
.

样例输出

1
4
3

思路

代码

#include <iostream>
#include <string.h>
using namespace std;
int arr[1000005], len;
int main()
{
    void set_naxt(char str[]);
    int I;
    char str[1000001];
    while (cin >> str && strcmp(str, ".") != 0)
    {
        set_naxt(str);
        if (len % (len - arr[len]) == 0)
            I = len / (len - arr[len]);
        else
            I = 1;
        cout << I << endl;
    }
}
void set_naxt(char str[])
{
    int i = 0, j = -1;
    arr[0] = -1;
    len = strlen(str);
    while (i < len)
    {
        if (j == -1 || str[i] == str[j])
        {
            i++; 
            j++;
            arr[i] = j;
        }
        else
            j = arr[j];
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 xingshuaikun@163.com。