2013年08月20日

兄弟数字


待字闺中的一道题,题目描述如下:

兄弟数字:给定一个数X,它的兄弟数字Y定义为:是由X中的数字组合而成,并且Y是大于X的数中最小的。例如:38276的兄弟数字是38627。给定X,求Y。

分析

由于是查找由X中的数字组合中比Y大且是最小的那个数,所以在排列X的数字组合时,要保证高位尽量相同,低位进行变换。对于数字38276来说,就是从最右边开始往前查找,如果右边的数字一直递增,则他们不可能排列出更小的数来了。例如76,则排列不出比76更小的。所以接着往左查找,找到第一个比上一个数小的。例如2比7小,则交换2与,76中第一个大于2的数,其余的然后按序排列。过程是,找到2,然后交换2与6,则是28672,然后交换72,则变成了28627。

如果给定的数是负数,则分析的过程还是一样,则变成了找第一个比上一个数大的。其余类似。

如果给定的数在(-10,10)之间,则没有兄弟数字。

代码

根据上面的分析写出代码。

#include<iostream>
#include<iterator>
#include<vector>

using namespace std;

void swap(int &a, int &b){
    if(&a == &b)
        return;
    a = a^b;
    b = a^b;
    a = a^b;
}

bool compareLarge(int a, int b){
    return a > b ? true : false;
}

bool compareSmall(int a, int b){
    return a < b ? true : false;
}

int getTheBrotherData(int data,bool positive,bool (*func)(int, int)){
    std::vector<int> vec; 
    while(data){
        vec.push_back(data % 10);
        data /= 10;
    }
    int len = vec.size(); 
    int i,record = vec[0];
    for(i = 0; i < len; i++){
        if(i+1 == len){
            cout << "This number is the largest!!!" << endl;
            return 0;
        }else{
            //if(vec[i] > vec[i+1])
            if(func(vec[i],vec[i+1]))
                break;
        }
    }
    int j = 0; 
    for(j; j <= i; j++){
        if(func(vec[j],vec[i+1]))
            break;
    }

    swap(vec[i+1],vec[j]);   
    j=0;
    while(j <= i/2){
        swap(vec[j],vec[i-j]);
        j++;
    }
    int newdata = 0;
    for(i= len-1; i >= 0 ;i--){
        newdata *= 10;
        newdata += vec[i];
    }

    return newdata;
}

int brotherData(int data){
    if(data > -10 && data < 10){
        cout << "please give another data which is not equal zero!" << endl;
        return 0;
    } 
    if(data > 0){
        return getTheBrotherData(data,true,compareLarge); 
    }else
        return 0 - getTheBrotherData(-data,false,compareSmall);
}

int main(){
    int data;
    while(cin >> data){
        cout << "data:" << data << endl;
        cout << "bro :" << brotherData(data) << endl;
    }
    return 0;
}
前一篇: 待字闺中之栅栏问题 后一篇: Openstack Eventlet分析(二)