Форум программистов, компьютерный форум CyberForum.ru

Нужен совет по решению - из двух натуральных чисел составить одно наименьшее. - C++

Восстановить пароль Регистрация
 
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
04.07.2013, 16:01     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее. #1
Минимальное число
Требуется написать программу, которая из цифр двух натуральных чисел создает наименьшее возможное число, сохраняя при этом порядок следования цифр в этих числах.
Пример:

Ввод:
125
34
Вывод:
12345

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>;
#include <iostream>;
 
using std::cin;
using std::cout;
 
int main (void)
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
        char A[256], B[256];
    cin >> A >> B;
    for(int i=0, z=0; ; )
    {
        if(!A[i] && !B[z]) break;
        if(!A[i]) { cout << B[z]; z++; continue;}
        if(!B[z]) { cout << A[i]; i++; continue;}
        if( A[i]==B[z] ) 
        { 
            if(A[i+1]=='\0' ) { cout << B[z]; z++; continue; }
            if(B[z+1]=='\0' ) { cout << A[i]; i++; continue; }
            if(A[i+1]<B[z+1]) { cout << A[i]; i++; } 
            else { cout << B[z]; z++; } continue; 
        }       
        if( A[i]<B[z]) { cout << A[i]; i++; }
        else { cout << B[z]; z++; }
    }
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.07.2013, 16:01     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее.
Посмотрите здесь:

Из цифр двух натуральных чисел составить наибольшее возможное число, сохраняя первоначальную последовательность цифр. C++
C++ Составить функцию, которая для двух натуральных чисел
C++ Найти наибольший общий делитель и наименьшее общее кратное двух введенных натуральных чисел.
C++ Определить наименьшее общее кратное двух натуральных чисел
Вывести наименьшее натуральное число, которое можно представить двумя разными способами в виде суммы кубов двух натуральных чисел C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.07.2013, 16:05     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее. #2
обычное слияние, только здесь цифры не обязательно упорядочены
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
04.07.2013, 16:12  [ТС]     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее. #3
Цитата Сообщение от Thinker Посмотреть сообщение
обычное слияние, только здесь цифры не обязательно упорядочены
Нет!!!! Это не обычное слияние. Прочтите внимательные!!! Если хотите приведите пример решения!!
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.07.2013, 16:14     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее. #4
ну как же не обычное, смысл тот же (пусть изначально данные и не упорядочены, там другой порядок нужен):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<stdio.h>
 
void F(char *a, char *b, char *c)
{
   int i, j, k;
   for(i = j = k = 0; a[i] && b[j]; )
      if (a[i] < b[j])
         c[k++] = a[i++];
      else c[k++] = b[j++];
   if (a[i])
      while(a[i])
         c[k++] = a[i++];
   else
      while(b[j])
         c[k++] = b[j++];
   c[k] = '\0';                      
}
 
int main()
{
   char a[] = "125", b[] = "34", c[256];
   F(a, b, c);
   puts(c);
   return 0;      
}
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
04.07.2013, 16:25  [ТС]     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее. #5
Цитата Сообщение от Thinker Посмотреть сообщение
ну как же не обычное, смысл тот же (пусть изначально данные и не упорядочены, там другой порядок нужен)
При слияние нужно сохранять порядок следования цифр в этих числах
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.07.2013, 16:27     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее. #6
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
При слияние нужно сохранять порядок следования цифр в этих числах
так порядок и сохраняется, в этом то и есть смысл слияния, как вы не поймете. Даже если изначально данные не были упорядочены, при таком слиянии они сохранят порядок и число будет минимальным при таком условии. с адресами красивее получается:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>
 
void F(char *a, char *b, char *c)
{
   while(*a && *b)
      if (*a < *b)
         *c++ = *a++;
      else *c++ = *b++;
   if (*a)
      while(*a)
         *c++ = *a++;
   else
      while(*b)
         *c++ = *b++;
   *c = '\0';                        
}
 
int main()
{
   char a[] = "125", b[] = "34", c[256];
   F(a, b, c);
   puts(c);
   return 0;      
}
gray_fox
What a waste!
 Аватар для gray_fox
1244 / 1127 / 53
Регистрация: 21.04.2012
Сообщений: 2,350
Завершенные тесты: 3
04.07.2013, 16:29     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее. #7
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
При слияние нужно сохранять порядок следования цифр в этих числах
Ну так он сохранится, в стандарной библиотеке даже есть отдельный алгоритм для этого...
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
04.07.2013, 16:42  [ТС]     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее. #8
Цитата Сообщение от Thinker Посмотреть сообщение
так порядок и сохраняется, в этом то и есть смысл слияния, как вы не поймете. Даже если изначально данные не были упорядочены, при таком слиянии они сохранят порядок и число будет минимальным при таком условии. с адресами красивее получается
А при вводе 32545 32545 будет 3232545545 а нужно 3232545455
Внимательные прочти задачу!
svk2140
-8 / 0 / 1
Регистрация: 04.07.2013
Сообщений: 254
04.07.2013, 16:51     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее. #9
не ну вы чё совсем с ума посходили вот очень просто прям простейши
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
int main()
{
    int a,b;
    cin >> a;
    cin >> b;
    for(int i = a;i < b;i++)
    {
        cout << i << endl;
    }
}
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
04.07.2013, 17:02  [ТС]     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее. #10
Цитата Сообщение от svk2140 Посмотреть сообщение
не ну вы чё совсем с ума посходили вот очень просто прям простейши
Я забил упомнить что ограничение 10255.
У вас даже на контрольном примере не работает!!!!
svk2140
-8 / 0 / 1
Регистрация: 04.07.2013
Сообщений: 254
04.07.2013, 17:05     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее. #11
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Я забил упомнить что ограничение 10255.
ну так просто больше ресурсов дать)

Добавлено через 55 секунд
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
Я забил упомнить что ограничение 10255.
У вас даже на контрольном примере не работает!!!!
всё у меня работает я что совсем чтоли не проверенные коды давать просто у тя наверное не win7
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.07.2013, 18:13     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее. #12
Цитата Сообщение от ALEXKIRNAS Посмотреть сообщение
А при вводе 32545 32545 будет 3232545545 а нужно 3232545455
Внимательные прочти задачу!
какой сердитый просто одно условие надо добавить:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>
 
void f(char *a, char *b, char *c)
{
   while(*a && *b)
      if (*a < *b || (*a == *b && !(*(b + 1))))
         *c++ = *a++;
      else *c++ = *b++;
   if (*a)
      while(*a)
         *c++ = *a++;
   else
      while(*b)
         *c++ = *b++;
   *c = '\0';                        
}
 
int main()
{
   char a[] = "32545", b[] = "32545", c[256];
   f(a, b, c);
   puts(c);
   return 0;      
}
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
04.07.2013, 18:52  [ТС]     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее. #13
Цитата Сообщение от Thinker Посмотреть сообщение
какой сердитый просто одно условие надо добавить:
Да ответ на этот тест верен. Я изменил твою программу и пустил на чекер. WA на 5 тесте.
Задача: http://********/index.asp?main=task&id_task=548.

Изменений код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<stdio.h>
#include <iostream>;
 
void f(char *a, char *b, char *c)
{
   while(*a && *b)
      if (*a < *b || (*a == *b && !(*(b + 1))))
         *c++ = *a++;
      else *c++ = *b++;
   if (*a)
      while(*a)
         *c++ = *a++;
   else
      while(*b)
         *c++ = *b++;
   *c = '\0';                        
}
 
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
   char a[256], b[256], c[515];
   std::cin >> a >> b;
   f(a, b, c);
   std::cout << c;
   return 0;      
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.07.2013, 19:28     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее. #14
да, там косяк имеется. а так?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<stdio.h>
 
int cmp(char *a, char *b)
{
   while (*a && *b && *a == *b)
   {
      ++a;
      ++b;
   }
   return !(*a) ? 1 : (!(*b) ? -1 : (*a < *b ? -1 : 1)); 
}
 
void f(char *a, char *b, char *c)
{
   while(*a && *b)
      if (*a < *b || (*a == *b && cmp(a, b) < 0))
         *c++ = *a++;
      else *c++ = *b++;
   if (*a)
      while(*a)
         *c++ = *a++;
   else
      while(*b)
         *c++ = *b++;
   *c = '\0';                        
}
 
int main()
{
   char a[] = "54", b[] = "55", c[256];
   f(a, b, c);
   puts(c);
   return 0;      
}
ALEXKIRNAS
10 / 10 / 2
Регистрация: 27.06.2013
Сообщений: 151
04.07.2013, 19:45  [ТС]     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее. #15
Вау!!!!!
Thinker - ты гений!!!!!!!
А теперь если не трудно можеш объяснить мне как это всё работает. Я пол дня ломал голову и не мог нечего придумать!!!!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.07.2013, 19:53     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее.
Еще ссылки по теме:

C++ Вычислить НОК (наименьшее общее кратное) двух натуральных чисел A и B
Найти наибольший общий делитель и наименьшее общее кратное двух введенных натуральных чисел C++
Вычислить наименьшее общее кратное двух натуральных чисел C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.07.2013, 19:53     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее. #16
не сразу верное решение, так как параллельно другими делами занимаюсь.
пробегаем, как в обычном слиянии цифры, но только отдельно рассматриваем случай равенства соответствующих цифр. например
a = ...5...
b = ...5...
1. если на цифре 5 число a заканчивается, то в с записываем цифру 5 из числа b

2. то же самое, только в 1. a и b меняем местами

3. пробегаем все цифры после 5, пока они равны, например
...5123...
...5123...
то есть пробегаем 5123, затем попадем либо в 1., либо в 2. (только относительно цифры 3), либо в случай, например
...51234...
...51237...
тогда 5 берем из a, так как 4 < 7
Yandex
Объявления
04.07.2013, 19:53     Нужен совет по решению - из двух натуральных чисел составить одно наименьшее.
Ответ Создать тему
Опции темы

Текущее время: 23:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru