сложный вопрос интервью в C - PullRequest
Новая
       9

сложный вопрос интервью в C

0 голосов
/ 23 марта 2011

В следующем вопросе:

Учитывая номер n, дай мне цифры (среди 3..5 и четного числа числа), чье добавление вернет Оригинальный номер. Полученные числа должен быть максимально сбалансированным, это означает, что вместо возврата 3 и 5, например, вернуть 4 и 4. Пример: 

7 = 3 + 4
16 = 4 + 4 + 4 + 4 rather than 3 + 5 + 4 + 4
24 = 12 + 12 or 6 + 6 + 6 + 6

Я подумал о следующем методе: 

splitnumber(int n)
{
    //check if the number is even
    if(n%2==0)
    {
        print(n/2,n/2);
        //check if x=2^m multiple exists or
        // not..like 4,8,16 etc
        print (n/x...n/x);
    }
    else //else if the no is odd... this part is incomplete
    {
        if(n-3>0)
        {
            print (3);

        }

        n-=3;
        if(n>0)
        {
            if (n>5)
            {
                print(3)
                n-=3;
            }
        }
    }
}

но я все еще не могу завершить все дела ... Как мне проверить, когда ответ имеет неуравновешенное решение ??

Ответы [ 2 ]

1 голос
/ 23 марта 2011

Вот мое решение, где результат будет идеально сбалансированным и с обнаружением невозможных случаев: 

vector<int> recursive_splitnumber(int n) {

    if (n <= 5) {
        return vector<int>(1,n);
    }

    int unbalancer = 0;
    vector<int> result1, result2;
    do {
        int val1, val2;
        if (n%2 == 0) {
            val1 = n%2 + unbalancer;
            val2 = n%2 - unbalancer;
        }
        else {
            val1 = (n-1)%2 + 1 + unbalancer;
            val2 = (n-1)%2 - unbalancer;
        }

        result1 = recursive_splitnumber(val1);
        result2 = recursive_splitnumber(val2);

        // Concatenate the result of the even and odd splits
        result1.insert(result1.end(),result2.begin(),result2.end());

        ++unbalancer;

    } while (result1.size()%2 != 0 && unbalancer <= 1);
    return result1;
}

bool splitnumber(int n) {
    vector<int> split = recursive_splitnumber(n);
    if (split.size()%2 == 0) {
        copy(split.begin(), split.end(), ostream_iterator<int>(cout, " "));
        return true;
    } else
        return false;
}

Это решение также будет учитывать случаи, такие как число 22, где сбалансированное деление дает 11 + 11(11 является числом, которое не может быть представлено с использованием данных правил), подразделение будет выполнено как 10 + 12, затем 5 + 5 + 6 + 6 и, наконец, 5 + 5 + 3 + 3 + 3 + 3.

1 голос
/ 23 марта 2011 
if (n < 4) print n;
else
    switch (n % 4)
        case 0: *print n/4 4's*
        case 1: *print n/4 - 1 4's* print 5
        case 2: *print n/4 - 1 4's* print 3 print 3
        case 3: *print n/4 4's* print 3

Немного неэффективная реализация в C # 

if (n < 4) Console.WriteLine(n);
else
    switch (n % 4)
    {
        case 0:
            Console.WriteLine(String.Join(" ", new string('4', n / 4).ToArray()));
            break;
        case 1:
            Console.WriteLine(
                (String.Join(" ", new string('4', n/4).ToArray().Skip(1)) + 
                " 5").TrimStart());
            break;
        case 2:
            Console.WriteLine(
                (String.Join(" ", new string('4', n/4).ToArray().Skip(1)) + 
                " 3 3").TrimStart());
            break;
        case 3:
            Console.WriteLine(String.Join(" ", new string('4', n/4).ToArray() + 
                " 3"));
            break;

    }
...