[HW] OJ记录20题之二

1 查找第一个只出现一次的字符

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

bool findChar(char *str, char *ch);

int main()
{
    char str[100];
    while (cin.getline(str, 100))
    {
        char ch;
        if (findChar(str, &ch))
        {
            cout<<ch<<endl;
        }
        else
        {
            cout<<"."<<endl;
        }
    }
}

bool findChar(char *str, char *ch)
{
    int c[256] = {0};
    for (int i = 0; i < strlen(str); i++)
    {
        c[str[i]]++;
    }

    for (int i = 0; i < strlen(str); i++)
    {
        if (c[str[i]] == 1)
        {
            *ch = str[i];
            return true;
        }
    }

    return false;
}

2 字符串排序

编写一个程序，将输入字符串中的字符按如下规则排序。
规则1：英文字母从A到Z排列，不区分大小写。
如，输入：Type 输出：epTy
规则2：同一个英文字母的大小写同时存在时，按照输入顺序排列。
如，输入：BabA 输出：aABb
规则3：非英文字母的其它字符保持原来的位置。
如，输入：By?e 输出：Be?y
样例：
输入：
A Famous Saying: Much Ado About Nothing(2012/8).
输出：
A aaAAbc dFgghh: iimM nNn oooos Sttuuuy (2012/8).

解题思路就是冒泡排序。

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

void sort(char *str);
bool isChar(char c);

int main()
{
    char str[100];
    while (cin.getline(str, 100))
    {
        sort(str);
        cout<<str<<endl;
    }

    return 0;
}

void sort(char *str)
{
    for (int i = 0; i < strlen(str) - 1; i++)
    {
        for (int j = 0; j < strlen(str) - i - 1; j++)
        {
            int m = j;
            // 增加这两个while是因为除字母外的其他字符要保持原位
            while (!isChar(str[m]) && m > 0)
            {
                m--;
            }
            int n = j + 1;
            while (!isChar(str[n]) && n < strlen(str) - 1)
            {
                n++;
            }
            int nm = str[m] >= 97 ? str[m] : str[m] + 32;
            int nn = str[n] >= 97 ? str[n] : str[n] + 32;
            if (isChar(str[m]) && isChar(str[n]) && nm > nn)
            {
                char c = str[m];
                str[m] = str[n];
                str[n] = c;
            }
        }
    }
}

bool isChar(char c)
{
    if ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'))
    {
        return true;
    }
    return false;
}

3 DNA序列

输入字符串和子串长度，得到CG比例最高的子串。
（建立一个长度为子串长度的窗口，然后向右移动窗口）

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

void fun(char *dest, const char *src, int n);

int main()
{
    char str[100];
    while (cin.getline(str, 100))
    {
        int n;
        cin>>n;
        char *dest = new char[n+1];
        fun(dest, str, n);
        cout<<dest<<endl;
        delete [] dest;
    }

    return 0;
}

void fun(char *dest, const char *src, int n)
{
    int len = strlen(src);
    int i = 0;
    int max_count = 0;
    int max_left = 0;
    int count = 0;
    int left = 0;
    while (i < n)
    {
        if (src[i] == 'C' || src[i] == 'G')
        {
            count++;
        }
        i++;
    }
    max_count = count;

    while (i < len)
    {
        int b1 = (src[i] == 'C' || src[i] == 'G');
        int b2 = (src[i - n] == 'C' || src[i - n] == 'G');
        left = i - n + 1;
        count += b1 - b2;
        if (count > max_count)
        {
            max_count = count;
            max_left = left;
        }
        i++;
    }

    while (n--)
    {
        *dest++ = src[max_left++];
    }
    *dest = '\0';
}

4 整形数组合并

未排序的数组合并，合并时要去除重复值

#include <iostream>
using namespace std;

void CombineBySort(int* pArray1,int iArray1Num,int* pArray2,int iArray2Num,int* pOutputArray,int *iOutputNum);
void sort(int *nums, int len);
void print(int *nums, int len);

int main()
{
    int n1;
    while (cin>>n1)
    {
        int *array1 = new int[n1];
        int i1 = 0;
        while(i1 < n1)
        {
            cin>>array1[i1++];
        }

        int n2;
        cin>>n2;
        int *array2 = new int[n2];
        int i2 = 0;
        while(i2 < n2)
        {
            cin>>array2[i2++];
        }

        int *array = new int[n1+n2];
        int n;
        CombineBySort(array1, n1, array2, n2, array, &n);
        print(array, n);

        delete [] array1;
        delete [] array2;
        delete [] array;
    }
    return 0;
}

void CombineBySort(int* pArray1,int iArray1Num,int* pArray2,int iArray2Num,int* pOutputArray,int* iOutputNum)
{
    sort(pArray1, iArray1Num);
    sort(pArray2, iArray2Num);
    int i1 = 0;
    int i2 = 0;
    int index = 0;
    int n;
    if (pArray1[i1] < pArray2[i2])
    {
        n = pArray1[i1];
        i1++;
        pOutputArray[index++] = n;
    }
    else
    {
        n = pArray2[i2];
        i2++;
        pOutputArray[index++] = n;
    }

    while (i1 < iArray1Num && i2 < iArray2Num)
    {
        if (pArray1[i1] <= pArray2[i2])
        {
            n = pArray1[i1];
            i1++;
        }
        else
        {
            n = pArray2[i2];
            i2++;
        }
        if (n != pOutputArray[index-1])
        {
            pOutputArray[index++] = n;
        }
    }

    while (i1 < iArray1Num)
    {
        if (pArray1[i1] != pOutputArray[index-1])
        {
            pOutputArray[index++] = pArray1[i1];
        }
        i1++;
    }

    while (i2 < iArray2Num)
    {
        if (pArray2[i2] != pOutputArray[index-1])
        {
            pOutputArray[index++] = pArray2[i2];
        }
        i2++;
    }

    *iOutputNum = index;
}

void sort(int *nums, int len)
{
    for (int i = 0; i < len - 1; i++)
    {
        for (int j = 0; j < len - i - 1; j++)
        {
            if (nums[j] > nums[j+1])
            {
                int temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
            }
        }
    }
}

void print(int *nums, int len)
{
    for (int i = 0; i < len; i++)
    {
        cout<<nums[i];
    }
    cout<<endl;
}

5 查找两个字符串a,b中的最长公共子串

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

char* fun(char *str1, char *str2, char *str);

int main()
{
    char str1[100];
    char str2[100];
    while (gets(str1) && gets(str2))
    {
        char str[100] = {0};
        cout<<fun(str1,str2,str)<<endl;;
    }
}

char* fun(char *str1, char *str2, char *str)
{
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int **c = new int*[len1 + 1];
    for (int i = 0; i < len1 + 1; i++)
    {
        c[i] = new int[len2 + 1];
    }

    for (int i = 0; i < len1 + 1; i++)
    {
        c[i][0] = 0;
    }

    for (int i = 0; i < len2 + 1; i++)
    {
        c[0][i] = 0;
    }

    int max = 0;
    int maxi = 0;
    int maxj = 0;
    for (int i = 1; i < len1 + 1; i++)
    {
        for (int j = 1; j < len2 + 1; j++)
        {
            if (str1[i - 1] == str2[j - 1])
            {
                c[i][j] = c[i - 1][j - 1] + 1;
                if (c[i][j] > max)
                {
                    max = c[i][j];
                    maxi = i;
                    maxj = j;
                }
            }
            else
            {
                c[i][j] = 0;
            }
        }
    }

    char *temp = str;
    int i = maxi;
    int j = maxj;
    while (c[i][j] > 0)
    {
        if (str1[i - 1] == str2[j - 1])
        {
            *temp++ = str1[i - 1];
        }
        i--;
        j--;
    }
    *temp = '\0';

    char *left = str;
    char *right = str + strlen(str) - 1;
    while (left < right)
    {
        char c = *left;
        *left++ = *right;
        *right-- = c;
    }

    return str;
}

6 成绩排序

输入数据组数，排序方式（升序或者降序），n组数据（由姓名和分数组成）。
输出最后的排序结果。

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

struct User
{
    char name[20];
    int val;
};

int main()
{
    int n;
    while (cin>>n)
    {
        int flag;
        cin>>flag;
        User *users = new User[n];
        int i = 0;
        while (i < n)
        {
            cin>>users[i].name;
            cin>>users[i++].val;
        }

        for (int i = 0; i < n - 1; i++)
        {
            int k = i;
            for (int j = i + 1; j < n; j++)
            {
                if ((flag == 1 && users[j].val < users[k].val) || (flag == 0 && users[j].val > users[k].val))
                {
                    k = j;
                }
            }

            if (k != i)
            {
                User temp = users[k];
                users[k] = users[i];
                users[i] = temp;
            }
        }

        for (int i = 0; i < n; i++)
        {
            cout<<users[i].name<<" "<<users[i].val<<endl;
        }
    }
}

7 汽水瓶

用空瓶子换汽水，三个空瓶换一瓶汽水。输入空瓶数目，输出可以换到的汽水数目。输入以0结束。

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

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

8 记负均正

输出负数的个数，以及正数的均值。均为为小数，则保留1位小数。

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

int main()
{
    int n;
    while (cin>>n)
    {
        if (n == 0)
        {
            cout<<"0 0";
            return 0;
        }
        int num;
        int c1 = 0;
        int c2 = 0;
        int sum = 0;
        int i = 0;
        while (i++ < n)
        {
            cin>>num;
            if (num > 0)
            {
                sum += num;
                c1++;
            }
            else if (num < 0)
            {
                c2++;
            }
        }

        sum % c1 == 0 ? printf("%d %d\n", c2, sum / c1) : printf("%d %.1f\n", c2, float(sum) / c1);
    }

    return 0;
}

9 字符串运用-密码截取

输入的字符为加入了前缀或者后缀字符的回文字符串，要求输出最长回文子串的长度。
输入：
ABBA
ABBA12
输出
4
4

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

void reverse(const char *str1, char *str2);
int fun(const char* str1, const char *str2);

int main()
{
    char str1[100];
    while (cin.getline(str1, 100))
    {
        char str2[100];
        reverse(str1, str2);
        cout<<fun(str1, str2)<<endl;
    }
    return 0;
}

void reverse(const char *str1, char *str2)
{
    int index = strlen(str1) - 1;
    while (index >= 0)
    {
        *str2++ = str1[index--];
    }
    *str2 = '\0';
}

int fun(const char* str1, const char *str2)
{
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int **c = new int*[len1 + 1];
    for (int i = 0; i <= len1; i++)
    {
        c[i] = new int[len2 + 1];
    }

    for (int i = 0; i <= len1; i++)
    {
        c[i][0] = 0;
    }

    for (int i = 0; i <= len2; i++)
    {
        c[0][i] = 0;
    }

    int m = 0;
    for (int i = 0; i <= len1; i++)
    {
        for (int j = 0; j <= len2; j++)
        {
            if (str1[i - 1] == str2[j - 1])
            {
                c[i][j] = c[i - 1][j - 1] + 1;
            }
            else
            {
                c[i][j] = 0;
            }
            m = max(m, c[i][j]);
        }
    }

    return m;
}

10 字符串分隔

输入：
abc
123456789
输出：
abc00000
12345678
90000000
（首先将字符串补成长度为8的倍数的字符串，然后输出）

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

int main()
{
    char str[108];
    while (cin.getline(str, 108))
    {
        int len = strlen(str);
        while (len % 8 != 0)
        {
            str[len] = '0';
            str[len + 1] = '\0';
            len++;
        }

        int i = 0;
        while (str[i] != '\0')
        {
            if ((i + 1) % 8 == 0)
            {
                cout<<str[i]<<endl;
            }
            else
            {
                cout<<str[i];
            }
            i++;
        }
    }
    return 0;
}

11 扑克牌大小

输入两手牌，输出较大的一手牌，若没有大小关系，则输出“ERROR”。
输入：
3-8
2-A
3 3 3-7 7 7
J J-8
4 4 4 4-joker JOKER
输出：
8
2
7 7 7
ERROR
joker JOKER
(对于每张牌，除J和JOKER外，比较第一个字符即可知道牌的大小)

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

enum Type
{
    GEZI = 1, DUIZI, SHUNZI, SANGE, ZHADAN, DUIWANG
};

char c[15][6] = {"3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A", "2", "joker", "JOKER"};
int n[15] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};

struct Cards
{
    Type type;
    int val;
};

int getCardValue(char ch);
int getCardNum(string str);
void format(string str, int n[]);
void nums2Card(int values[], int n, Cards& C);
int cmp(Cards C1, Cards C2);

int main()
{
    char str[100];
    while (cin.getline(str, 100))
    {
        string str1 = "";
        string str2 = "";
        int i = 0;
        while (str[i] != '-')
        {
            str1 += str[i++];
        }
        i++;
        while (str[i] != '\0')
        {
            str2 += str[i++];
        }

        int cardNum1 = getCardNum(str1);
        int cardNum2 = getCardNum(str2);
        int nums1[5] = {0};
        int nums2[5] = {0};
        format(str1, nums1);
        format(str2, nums2);
        Cards hand1;
        Cards hand2;
        nums2Card(nums1, cardNum1, hand1);
        nums2Card(nums2, cardNum2, hand2);
        if (cmp(hand1, hand2) == 1)
        {
            cout<<str1.c_str()<<endl;
        }
        else if (cmp(hand1, hand2) == -1)
        {
            cout<<str2.c_str()<<endl;
        }
        else
        {
            cout<<"ERROR"<<endl;
        }
    }
    return 0;
}

int getCardValue(char ch)
{
    for (int i = 0; i < 15; i++)
    {
        if (ch == c[i][0])
        {
            return n[i];
        }
    }
    return -1;
}

int getCardNum(string str)
{
    int count = 0;
    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] == ' ')
        {
            count++;
        }
    }
    return count + 1;
}

void format(string str, int n[])
{
    int card_index = 0;
    int i = 0;
    while(i < str.size())
    {
        if (str[i] != ' ')
        {
            int card_value;
            if (str[i] == 'J' && i + 1 < str.size() && str[i + 1] == 'O')
            {
                card_value = 15;
            }
            else
            {
                card_value = getCardValue(str[i]);
            }
            n[card_index++] = card_value;
            while(i < str.size() && str[i] != ' ')
            {
                i++;
            }
        }
        else
        {
            i++;
        }
    }
}

void nums2Card(int values[], int n, Cards& C)
{
    if (n == 1)
    {
        C.type = (Type)1;
        C.val = values[0];
    }
    else if (n == 2)
    {
        if (values[0] == values[1])
        {
            C.type = (Type)2;
            C.val = values[0];
        }
        else if (values[0] + values[1] == 29)
        {
            C.type = (Type)6;
            C.val = 15;
        }
    }
    else if (n == 3 && values[0] == values[1] && values[1] == values[2])
    {
        C.type = (Type)4;
        C.val = values[0];
    }
    else if (n == 4 && values[0] == values[1] && values[1] == values[2] && values[2] == values[3])
    {
        C.type = (Type)5;
        C.val = values[0];
    }
    else if (n == 5)
    {
        int diff = values[1] - values[0];
        if (values[2] - values[1] == diff && values[3] - values[2] == diff && values[4] - values[3] == diff)
        C.type = (Type)3;
        C.val = values[0];
    }
    else
    {
        C.type = (Type)0;
        C.val = 0;
    }
}

int cmp(Cards C1, Cards C2)
{
    if (C1.type < 5 && C2.type < 5)
    {
        if (C1.type == C2.type)
        {
            return C1.val > C2.val ? 1 : -1;
        }
    }
    else
    {
        if (C1.type == C2.type)
        {
            return C1.val > C2.val ? 1 : -1;
        }

        return C1.type > C2.type ? 1 : -1;
    }

    return 0;
}

12 输入一行字符，分别统计出包含英文字母、空格、数字和其它字符的个数

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

int main()
{
    char ch[100];
    while (cin.getline(ch, 100))
    {
        int en = 0;
        int blank = 0;
        int num = 0;
        int other = 0;
        for (int i = 0; i < strlen(ch); i++)
        {
            if ((ch[i] >= 'A' && ch[i] <= 'Z') || (ch[i] >= 'a' && ch[i] <= 'z'))
            {
                en++;
            }
            else if (ch[i] == ' ')
            {
                blank++;
            }
            else if (ch[i] >= '0' && ch[i] <= '9')
            {
                num++;
            }
            else
            {
                other++;
            }
        }
        cout<<en<<endl<<blank<<endl<<num<<endl<<other<<endl;
    }
    return 0;
}

13 统计每个月兔子的总数

第一个月—————–1
第二个月—————–1
第三个月—————–2
第四个月—————–3
第五个月—————–5
第六个月—————–8
第七个月—————–13

#include <iostream>
using namespace std;

int main()
{
    int n;
    while (cin>>n)
    {
        int a = 0;
        int b = 1;
        int c;
        int i = 2;
        while (i <= n)
        {
            c = a + b;
            a = b;
            b = c;
            i++;
        }
        cout<<c<<endl;
    }
    return 0;
}

14 质数因子

找出输入整数的所有质数因子
输入：180
输出：2 2 3 3 5

#include <iostream>
using namespace std;

bool isPrime(int n);

int main()
{
    int n;
    while (cin>>n)
    {
        int i = 2;
        while (n != 1)
        {
            while (isPrime(i) && n % i == 0)
            {
                cout<<i<<" ";
                n /= i;
            }
            i++;
        }
    }
    return 0;
}

bool isPrime(int n)
{
    for (int i = 2; i <= n / 2; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }

    return true;
}

15 自守数

一个数的平方的尾数等于该自然数本身的数。（252=625）
输入：
2000
输出：8
思路：（625 - 25） % 100 == 0？

#include <iostream>
using namespace std;

int getBit(int n);
int fun(int n);

int main()
{
    int n;
    while (cin>>n)
    {
        cout<<fun(n)<<endl;
    }
    return 0;
}

int getBit(int n)
{
    int b = 0;
    while (n / 10 != 0)
    {
        b++;
        n /= 10;
    }

    int x = 10;
    for (int i = 0; i < b; i++)
    {
        x *= 10;
    }

    return x;
}

int fun(int n)
{
    int count = 0;
    for (int i = 0; i <= n; i++)
    {
        int b = getBit(i);
        if ((i * i - i) % b == 0)
        {
            count++;
        }
    }

    return count;
}

16 iNOC产品部–完全数计算

完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。
它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。
例如：28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28。
给定函数count(int n),用于计算n以内(含n)完全数的个数。计算范围, 0 < n <= 500000
返回n以内完全数的个数。异常情况返回-1

#include <iostream>
using namespace std;

int fun(int n);

int main()
{
    int n;
    while (cin>>n)
    {
        int count = 0;
        for (int j = 2; j <= n; j++)
        {
            int sum = 0;
            for (int i = 1; i <= j / 2; i++)
            {
                if (j % i == 0)
                {
                    sum += i;
                }
            }
            if (sum == j)
            {
                count++;
            }
        }
        cout<<count<<endl;
    }
}

17 人民币转换

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

string big[10] = {"零","壹","贰","叁","肆","伍","陆","柒","捌","玖"};

int dotIndex(string str);
int atoi(string str, int i, int j);
void toChinese(int n, string& str);

int main()
{
    string s;
    while (getline(cin,s))
    {
        int di = dotIndex(s);
        int left; //小数点左边数字的大小
        int right; //小数点右边数字的大小
        if (di != -1)
        {
            left = atoi(s, 0, di - 1);
            right = atoi(s, di + 1, s.size() - 1);
        }
        else
        {
            left = atoi(s, 0, s.size() - 1);
            right = 0;
        }

        string str = "人民币";
        toChinese(left, str);
        str += "元";
        if (right == 0)
        {
            str += "整";
        }
        else
        {
            int jiao = right / 10;
            if (jiao != 0)
            {
                str += big[jiao];
                str += "角";
            }
            else
            {
                str += "零";
            }
            int fen = right % 10;
            if (fen != 0)
            {
                str += big[fen];
                str += "分";
            }
        }

        string temp = str.substr(6, 4);
        if (temp.compare("壹拾") == 0)
        {
            str.replace(6,4,"拾");
        }
        cout<<str.c_str()<<endl;
    }
}

int dotIndex(string str)
{
    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] == '.')
        {
            return i;
        }
    }
    return -1;
}

int atoi(string str, int i, int j)
{
    int n = 0;
    for (int k = i; k <= j; k++)
    {
        n = 10 * n + str[k] - '0';
    }

    return n;
}

void toChinese(int n, string& str)
{
    int b[6] = {100000000,10000,1000,100,10,1};
    string c[6] = {"亿","万","仟","佰","拾",""};
    bool stat[6] = {false};

    for (int i = 0; i < sizeof(b)/sizeof(b[0]); i++)
    {
        int temp = n / b[i];
        if (temp != 0)
        {
            if (stat[i-1] && str.size() != 6)
            {
                str += "零";
            }
            if (temp > 10)
            {
                toChinese(temp, str);
            }
            else
            {
                str += big[temp];
            }
            str += c[i];
        }
        else
        {
            stat[i] = true;
        }
        n %= b[i];
    }
}

18 矩阵乘法

#include <iostream>
using namespace std;

int main()
{
    int x, y, z;
    while (cin>>x>>y>>z)
    {
        int m1[100][100];
        int m2[100][100];
        int r[100][100] = {0};
        for (int i = 0; i < x; i++)
        {
            for (int j = 0; j < y; j++)
            {
                cin>>m1[i][j];
            }
        }

        for (int i = 0; i < y; i++)
        {
            for (int j = 0; j < z; j++)
            {
                cin>>m2[i][j];
            }
        }

        for (int i = 0; i < x; i++)
        {
            for (int j = 0; j < z; j++)
            {
                for (int k = 0; k < y; k++)
                {
                    r[i][j] += m1[i][k] * m2[k][j];
                }

                if (j == z - 1)
                {
                    cout<<r[i][j]<<endl;
                }
                else
                {
                    cout<<r[i][j]<<" ";
                }
            }
        }
    }
}

19 记负均正

输入n个int数，输出负数格式及整数的均值。

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

int main()
{
    int n;
    int zh = 0;
    int fu = 0;
    int sum = 0;
    while (cin>>n)
    {
        if (n > 0)
        {
            zh++;
            sum += n;
        }
        else
        {
            fu++;
        }
    }
    cout<<fu<<endl;
    printf("%.1f\n", zh == 0 ? zh : float(sum) / zh);
}

20 查找组成一个偶数最接近的两个素数

首先标记处素数（>=2），然后逐对判断。判断第一个数小于第二个数的即可（diff>0）。

#include <iostream>
using namespace std;

int main()
{
    const int MAX = 10001;
    bool b[MAX];
    for (int i = 0; i < MAX; i++)
    {
        if (i & 0x1)
        {
            b[i] = true;
        }
        else
        {
            b[i] = false;
        }
    }
    b[2] = true;

    for (int i = 3; i < MAX; i++)
    {
        for (int j = 2; j * i < MAX; j++)
        {
            b[i * j] = false;
        }
    }

    int n;
    while (cin>>n)
    {
        int min = 0x7fffffff;
        int x = 0, y = 0;
        int diff;
        for (int i = 2; i < n; i++)
        {
            if (b[i] && b[n - i])
            {
                diff = n - 2 * i;
                if (diff > 0 && diff < min)
                {
                    min = diff;
                    x = i;
                    y = n - i;
                }
            }
        }
        cout<<x<<endl<<y<<endl;
    }
}
时间： 2024-10-18 13:44:38

[HW] OJ记录20题之二的相关文章

[HW] OJ记录20题之四

1 表示数字 #include <iostream> #include <string> using namespace std; int main() { string str; while (cin>>str) { string res = ""; for (int i = 0; i < str.size(); i++) { if (str[i] >= '0' && str[i] <= '9') { if (i

[HW] OJ记录20题之一

注意 int main() { int n; cin>>n; while (n--) { char ch[100]; cin>>ch; //此处用gets(ch)或者cin.getline(ch,100)出现问题 //原因在于输入n后残留了一个回车键,可用getchar()获取. cout<<fun(ch)<<endl; } return 0; } 1 删除字符串中出现次数最少的字符 特殊案例(输入:aaa,输出:NULL) #include <ios

[HW] OJ记录20题之三

1 字符串最后一个单词的长度 #include <iostream> using namespace std; int main() { char ch[128]; while (cin.getline(ch, 128)) { int len = 0; for (int i = 0; ch[i] != '\0'; i++) { if (ch[i] == ' ') { len = 0; } else { len++; } } cout<<len<<endl; } } 2

c++-一道OJ上的题，数的划分，求大神解答

问题描述 一道OJ上的题,数的划分,求大神解答 有N个排列好的数,不改变排列次序,要分成K个部分,每个部分至少有一个数, (其中K <=N),若将每一个部分的数相乘,然后将K个部分相加,则可以得到一个表达式,求这个表达式的最大数值. 输入格式文件第一行为2个整数N.K下面N行为N个整数(N<=100,整数的范围都在整型以内)样例输入5 2 12345 样例输出121 我的思路是动态规划:以f(ij)表示分成i组,最后一个数是j的最大数值.以下是我的代码: #include <iostre

JAVA认证历年真题解析二（附答案）

问题描述 我在网上偶然看到一个网站,这个网站里面的资料非常全,除了一些免费的资料,还有网络视频,觉得非常不错,大家有兴趣或者需要,可以去看看[中华IT学习网]www.100itxx.com内容介绍>>本试卷共有45道题,每题后面都有详细解析.例:1.Whichofthefollowingrangeofshortiscorrect?A.-27--27-1B.0--216-1C.?215--215-1D.?231--231-1翻译下面哪些是short型的取值范围.答案 C解析 短整型的数据类型的长

分页显示Oracle数据库记录的类之二

oracle|分页|数据|数据库|显示 //-------------------------------- // 工作函数 //-------------------------------- //读取记录 // 主要工作函数,根据所给的条件从表中读取相应的记录 // 返回值是一个二维数组,Result[记录号][字段名] function ReadList() { $SQL="SELECT * FROM ".$this->Table." ".$this-&

分页显示Oracle数据库记录的类之二_php基础

//-------------------------------- // 工作函数 //-------------------------------- //读取记录 //主要工作函数,根据所给的条件从表中读取相应的记录 //返回值是一个二维数组,Result[记录号][字段名] function ReadList() { $SQL="SELECT * FROM ".$this->Table." ".$this->Condition." OR

《三国之天》20日开启二测增加用户教程系统

(编译/小熙)以"一个伟大战役的开始"为口号的,韩国韩光软件10年度网游巨献<三国之天>将于20日起开启第二次内部测试,今天韩光官方正式公布二测内容. 在即将到来的二测中,<三国之天>将为大家提供全新的邮件系统以及商业交易系统.让大家在游戏中更加方便.舒适的进行体验. 另外<三国之天>将通过自制.全新的XG引擎系统为玩家提供磅礴大气的战场场面.而韩光软件方面表示,全新的XG引擎系统,通过对系统的优化,可以让一些低端配置的机器同样能用流畅运转<三

数据库记录安全解决方案（二）

数据库记录安全解决方案 http://netkiller.github.io/journal/mysql.security.html Mr. Neo Chen (netkiller), 陈景峰(BG7NYT) 中国广东省深圳市龙华新区民治街道溪山美地518131+86 13113668890+86 755 29812080<netkiller@msn.com> 版权 2014 http://netkiller.github.io 版权声明 转载请与作者联系,转载时请务必标明文章原始出处和作者信