On-line: гостей 0. Всего: 0 [подробнее..]
Программисты всех стран, объединяйтесь!

АвторСообщение



ссылка на сообщение  Отправлено: 19.06.18 16:17. Заголовок: Построение наименьшего числа из цифр заданного числа без использования массива.


Вот еще одна интересная задача на работу с числами, то есть на преобразование чисел без использования массивов, встреченная мною на сайте Stackoverflow

Forming the smallest number-

Требуется по заданному числу построить новое число таким образом, чтобы в нем не повторялись одинаковые цифры исходного числа, и при этом полученное число, состоящее из уникальных цифр исходного числа, было минимальным. При этом нельзя использовать массивы. А это означает, что нельзя также использовать строки.

Опять-таки, эта задача была задана на интервью.

Как я уже писал в другой теме, никогда не делайте никаких тестовых заданий на интервью. Интервью - это беседа, а не экзамен. То есть не позволяйте манипулировать вами и распоряжаться вашим временем по прихоти кого-либо.

Но вернемся к самой задаче.

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

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

 
#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 ) );
}


Вывод программы на консоль может выглядеть, например, следующим образом

 
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


Спасибо: 0 
ПрофильЦитата Ответить
Новых ответов нет


Ответ:
1 2 3 4 5 6 7 8 9
большой шрифт малый шрифт надстрочный подстрочный заголовок большой заголовок видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки моноширинный шрифт моноширинный шрифт горизонтальная линия отступ точка LI бегущая строка оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 11
Права: смайлы да, картинки да, шрифты да, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет