Форум » C/C++ для начинающих (C/C++ for beginners) » Построение наименьшего числа из цифр заданного числа без использования массива. » Ответить
Построение наименьшего числа из цифр заданного числа без использования массива.
Сыроежка: Вот еще одна интересная задача на работу с числами, то есть на преобразование чисел без использования массивов, встреченная мною на сайте Stackoverflow Forming the smallest number- Требуется по заданному числу построить новое число таким образом, чтобы в нем не повторялись одинаковые цифры исходного числа, и при этом полученное число, состоящее из уникальных цифр исходного числа, было минимальным. При этом нельзя использовать массивы. А это означает, что нельзя также использовать строки. Опять-таки, эта задача была задана на интервью. Как я уже писал в другой теме, никогда не делайте никаких тестовых заданий на интервью. Интервью - это беседа, а не экзамен. То есть не позволяйте манипулировать вами и распоряжаться вашим временем по прихоти кого-либо. Но вернемся к самой задаче. Напрашивается подход к решению задачи с использованием сортировки вставкой, где сортируемыми элементами являются цифры числа. То есть для каждой цифры исходного числа нужно пройтись по цифрам формируемого числа и найти в формируемом числе позицию, куда надо вставить заданную цифру при условии, что в формируемом числе эта цифра пока еще отсутствует. Ниже приведена демонстрационная программа, в которой показано, как это можно сделать. Честно признаюсь, я особо не тестировал свою программу, но по произвольно заданным числам она показывает требуемый результат. Не стесняйтесь сообщить в этой теме, если найдете баг в программе, а также можете представить свои решения этой задачи. [pre2] #include <stdio.h> #include <stdlib.h> unsigned long long int smallest_unique_number( unsigned long long int n ) { const unsigned long long int Base = 10; unsigned long long int m = 0; do { unsigned long long int digit = n % Base; if ( digit ) { unsigned long long int i = 1; unsigned long long int numer, denom; while ( numer = m / i, denom = m % i, numer != 0 && digit < numer % Base ) i *= Base; if ( numer % Base < digit ) { numer = numer * Base + digit; m = numer * i + denom; } } } while ( n /= Base ); return m; } int main( void ) { while ( 1 ) { printf( "Enter a non-negative number (0 - exit): " ); unsigned long long n; if ( scanf( "%llu", &n ) != 1 || n == 0 ) break; printf( "\nThe smallest unique number formed from %llu is %llu\n\n", n, smallest_unique_number( n ) ); } printf( "\nThe smallest unique number formed from %llu is %llu\n\n", 0llu, smallest_unique_number( 0llu ) ); } [/pre2] Вывод программы на консоль может выглядеть, например, следующим образом [pre2] Enter a non-negative number (0 - exit): 1 The smallest unique number formed from 1 is 1 Enter a non-negative number (0 - exit): 2 The smallest unique number formed from 2 is 2 Enter a non-negative number (0 - exit): 10 The smallest unique number formed from 10 is 1 Enter a non-negative number (0 - exit): 11 The smallest unique number formed from 11 is 1 Enter a non-negative number (0 - exit): 13 The smallest unique number formed from 13 is 13 Enter a non-negative number (0 - exit): 132 The smallest unique number formed from 132 is 123 Enter a non-negative number (0 - exit): 991233612 The smallest unique number formed from 991233612 is 12369 Enter a non-negative number (0 - exit): 0 The smallest unique number formed from 0 is 0 [/pre2]
Ответов - 0
полная версия страницы