#recursion #dynamic
Вопрос:
Я новичок, пытающийся самостоятельно изучать C, и на днях у меня возникла проблема, которую, как я думал, было бы здорово попытаться решить с помощью короткой программы. Мне оказалось, что решить эту проблему немного сложнее, чем я изначально думал. В основном проблема заключается в следующем.
Я хочу иметь возможность вводить одно значение int между 0..255 (никогда не выходящее за пределы этого диапазона) в функцию, а внутри функции есть массив из 8 значений (1, 2, 4, 8, 16, 32, 64, 128), которые можно объединить, сложив вместе, чтобы получить единственное значение int. А затем верните возможные различные комбинации. Т. е.
Задача 192
Возвращает 64, 128
Из того, что я прочитал, это проблема подмножества, и ее можно решить с помощью рекурсии, но я действительно изо всех сил пытаюсь применить теорию и примеры, которые я нашел, на практике. Если бы кто-нибудь мог мне помочь или даже направить меня в правильном направлении, чтобы попытаться решить эту проблему.
Комментарии:
1. Вы говорите, что хотите «различные возможные комбинации», но уверены ли вы, что хотите более одного решения? Я бы предположил, что вам нужно только (уникальное) решение, которое использует значение только один раз. Например,
192 = 128 32 32, но я предполагаю, что вам не нужно это решение.
Ответ №1:
Подсказка: попробуйте использовать оператор «побитовое и» ( amp; )
Ответ №2:
Прежде всего, рекомендуется разделять ввод-вывод и алгоритмы. Таким образом, вы, как правило, не должны разрабатывать функции, которые принимают пользовательский ввод и одновременно выполняют какой-либо алгоритм.
Следующее «может быть решено с помощью рекурсии» — это не самоцель. Рекурсия опасна, неэффективна и трудна для чтения. Существует очень мало случаев, когда его следует использовать в программировании на C, и нет случаев, когда новички вообще должны его использовать. В большинстве случаев рекурсия в C просто сводится к следующему: «Я мог бы нарисовать этот сарай, одновременно стоя на руках»… ну, может быть, вы могли бы, может быть, вы могли бы сделать это без риска сломать себе шею, может быть, вы даже можете сделать это так быстро, как если бы вы стояли прямо (маловероятно), но зачем вам это делать?
Помимо дизайна программы, алгоритм, который вы ищете, тесно связан с двоичными числами. Любое число в любой базе может быть образовано:
цифра n * основание n цифра n-1 * основание n-1… цифра 0 * основание 0.
В случае двоичных (основание 2) чисел вручную, например, 111 может быть вручную декодировано в десятичное число, как:
1 * 2 2 1 * 2 1 1 * 2 0 = 4 2 1 десятичная дробь = 7 десятичных знаков.
Теперь, если мы сравним это с вашим алгоритмом, приведенные выше множители для базы 2 соответствуют 1, 2, 4, 8…
Удобно, что все числа в C на самом деле являются необработанными двоичными. Они переводятся на другие базы только при вводе/выводе данных пользователем. Поэтому то, что вам нужно для вашего алгоритма, — это просто способ проверить, установлены отдельные цифры двоичного числа или нет.
Это можно сделать с amp; помощью операторов «побитовое И» и << «побитовое смещение влево». Побитовое смещение влево для сдвига значения 1 влево, чтобы получить различные множители: 0b=0, 1b=1, 10b=2, 100b=4 и так далее. А затем побитово И замаскировать отдельный бит от остальных, чтобы увидеть, установлен он или нет. Если он не установлен, что ж, тогда по приведенной выше формуле мы получим 0*основание n для этой цифры, так что она будет равна нулю и может быть проигнорирована.
Написать реальный код на C для этого на самом деле довольно просто:
for(int i=0; i<8; i )
{
unsigned int mask = 1u << i;
if(mask amp; number)
{
printf("%un", mask);
}
}
(Это использование беззнаковых чисел, чтобы избежать различных распространенных ошибок, но это отдельная тема.)
Комментарии:
1. Я думаю, что ОП хотел узнать о рекурсии и арифметике, и вместо этого этот ответ говорит им забыть об арифметике и рекурсии и использовать побитовые операторы и циклы. Ваш код, безусловно, более эффективен, и циклы и побитовые операторы заслуживают изучения, но если в данный момент OP изучает рекурсию и арифметические операторы, это немного не по теме для них.
2. @Stef Я предполагаю, что они хотят стать хорошим программистом. Если кто-то хочет научиться рисовать сараи, стоя на руках, я должен научить их: не делайте этого, это глупо, опасно и неэффективно, и от этого абсолютно ничего не выиграешь. Сделайте это как можно быстрее и проще, стоя прямо. Не практикуйте плохие привычки, иначе вы начнете использовать плохие привычки для создания плохих программ.
3. Хороший программист должен понимать сходства и различия между использованием
/и%и использованием<<и.amp;Но они этого не сделают, если не узнают об/этом%первыми. Кроме того, ваше утверждение «рекурсия опасна, неэффективна и трудночитаема», на мой взгляд, вводит в заблуждение. Циклы также могут быть опасными, неэффективными и трудночитаемыми. Хороший способ избежать написания опасного кода-это на самом деле изучить код, а не слушать, как вам говорят: «Не изучайте это, это все равно, что стоять на руках».4. Кстати, после нескольких лет опыта у меня сложилось мнение, что студенты, которые сначала изучают рекурсию, а затем циклы, обычно пишут гораздо лучший код, чем студенты, которые сначала изучают циклы, а затем рекурсию. Рекурсия на самом деле гораздо более естественна, чем циклы. Многие люди «боятся» рекурсии и начинают иррационально мыслить, когда речь заходит о рекурсии, потому что сначала они узнали о циклах. Все это очень нелогично, когда рекурсия гораздо более естественно следует человеческой логике.
5. @Stef Проблема в том, что вам вообще не следует изучать рекурсию, потому что ее практически никогда не следует использовать. Основными проблемами являются пиковое использование стека и блокировка оптимизации компилятора. Очень важно иметь код, который не вызывает переполнения стека и не выполняется ужасно медленно. В то время как контраргумент «это кажется более естественным» является субъективной бессмыслицей. Создавайте программы, которые безопасны и быстры, и точка.