C # - 1 2 4 8 16 32 64 ... series - Найти индексы на основе входного номера, рекурсивная функция? - PullRequest
Новая
       16

C # - 1 2 4 8 16 32 64 ... series - Найти индексы на основе входного номера, рекурсивная функция?

3 голосов
/ 30 марта 2011

У меня есть серия чисел как таковая: [1 2 4 8 16 32 64 128], если я ввожу число, то есть 66, то на выходе должно быть 64 и 2. Если я введу 87, то на выходе должно быть 64, 16, 4,2, 1.

(По сути, сначала делим на максимально возможное число, находим остаток, затем продолжаем делить на максимально возможное число, пока остаток не станет 0. Или другой способ, возможно, просто вычесть наибольшеевозможное число и продолжайте вычитать так, пока оно не достигнет 0.)

Я думаю о рекурсивной функции, но не совсем уверен.Любая помощь?

Спасибо.

Ответы [ 9 ]

10 голосов
/ 30 марта 2011 
class Program
{
    [Flags]
    enum Bits
    {
        _1 = 1,
        _2 = 2,
        _4 = 4,
        _8 = 8,
        _16 = 16,
        _32 = 32,
        _64 = 64,
        _128 = 128
    }

    static void Main(string[] args)
    {
        var b = (Bits)87;
        Console.WriteLine(b);
        Console.ReadKey();
    }
}
3 голосов
/ 30 марта 2011

Вот итерационная версия 

public static IEnumerable<int> FindIndex(int input)
{
    var power = 0;
    while (input > 0)
    {
        var digit = input % 2;
        if (digit == 1)
        {
            yield return (int)Math.Pow(2, power);
        }
        input /= 2;
        power++;
    }
}

и вот рекурсивная версия 

public static void FindIndexRec(int input, int power, ICollection<int> numbers)
{
    if (input == 0)
    {
        return;
    }
    var digit = input % 2;
    if (digit == 1)
    {
        numbers.Add((int)Math.Pow(2, power));
    }
    FindIndexRec(input / 2, ++power, numbers);
}

и вы можете назвать это как 

var numbers = new List<int>();
FindIndexRec(input, 0, numbers);
2 голосов
/ 30 марта 2011

Вы можете использовать битовые маски. Фактически, поцарапайте это - вы должны использовать битовые маски! Это почти наверняка, как код ошибки был создан, и это, как это должно быть выделено. Все остальное может привести в замешательство вашу аудиторию других программистов.

Я не претендую на то, чтобы представлять всех программистов, и при этом я не претендую на то, чтобы быть хорошим, но я программист, и все остальные ответы смутили меня. Это, очевидно, побитовая «проблема», так зачем запутывать?

Нет необходимости хранить результаты в любом месте, так как каждый раз пересчитывать результат так же быстро, например: 

for(int i=0;i<8;++i) {
    if((error&(1<<i))!=0 {
        // 1<<i is in the resulting list.
    }
}
1 голос
/ 10 января 2018 
    IEnumerable<int> GetFlags(int input,IEnumerable<int> series)
    {
        foreach (int value in series)
            if ((input & value)==value)
                yield return value;
    }

Или LINQ решение проблемы. 

IEnumerable<int> GetFlags(int input, IEnumerable<int> series)
{
    return series.Where(x => (x & input) == x);
}
0 голосов
/ 10 января 2018

Программирование в стороне, вы также можете посмотреть на это математическиЭто в основном 2 в степени (целочисленное значение) log(2, input)

Поместить это в рекурсивную функцию было бы легко, конечно, это выглядело бы просто и гладко, но я сомневаюсь, что это менее сложно в вычислительном отношении, и этоконечно, не поможет с твоей домашней работой, просто подумал, что я ее сюда брошу.

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

Этот будет работать с входными номерами больше 256: 

   int[] calculate(int input)
    {
        List<int> retVal = new List<int>();
        string output = string.Empty;
        int[] series = new int[] { 1, 2, 4, 8, 16, 32, 64, 128 };
        foreach (int i in series.Reverse<int>())
        {
            while (input >= i)
            {
                retVal.Add(i);
                input -= i;
            }
        }

        return retVal.ToArray();
    }

Пример: var result = Calculate (284);// результат = 128, 128, 16, 8, 4

0 голосов
/ 30 марта 2011 
List<int> additives = new List<int>()
List<int> sourceNumbers = new List<int> { 1, 2, 4, 8, 16, 32, 64, 128 };

int sourceNumber = 87;

foreach(var number in sourceNumbers.Reverse())
{
    if(sourceNumber % number > 0)
    {
       additives.Add(number);
       sourceNumber -= number;
    }
    else
    {
       additives.Add(number);
       break;
    }
}
0 голосов
/ 30 марта 2011 
    string calculate(int input)
    {
        string output = string.Empty;
        int[] series = new int[] { 1, 2, 4, 8, 16, 32, 64, 128 };
        foreach (int i in series.Reverse<int>())
        {
            if (input >= i)
            {
                output += i.ToString() + " ";
                input -= i;
            }
        }
        return output;
    }
0 голосов
/ 30 марта 2011

Вот довольно наивное итеративное решение в псевдокоде. Попробуйте взять это где-то более интересным отсюда. Вы можете сделать это рекурсивно, вы можете преобразовать целое число в двоичное представление и выполнить итерацию в этой строке, если представить, что есть очень умный способ сделать это с помощью LINQ очень кратко и т. Д. 

v = inputNumber
while(v > 0):
     temp = greatest power of 2 less than v
     print temp
     v -= temp

PS - это явно не хранит серию, о которой идет речь - оно предполагает степень 2.

...