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

Прошу помощи по коду (нужен алгоритм) - C++

Восстановить пароль Регистрация
 
~aspro~
 Аватар для ~aspro~
0 / 0 / 0
Регистрация: 24.05.2011
Сообщений: 21
12.09.2011, 01:22     Прошу помощи по коду (нужен алгоритм) #1
Условие задачи:
Дано 36-ричное число, содержащее не более 100 цифр (цифры 10,11,...,35 кодируются заглавными латинскими буквами А,В,...,Z). Переставить цифры числа таким образом, чтобы оно стало "счастливым". "Счастливым" будем называть число из N цифр, у которого сумма первых [N/2] цифр равна сумме последних [N/2] цифр. Если такая перестановка невозможна, вывести сообщение "impossible"

Код программы:
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include "stdafx.h"
#include "iostream"
#include "windows.h"
#include "conio.h"
using namespace std;
char ch[100],                                         
     mas_36[36]={
                 '0','1','2','3','4','5','6','7','8', 
                 '9','A','B','C','D','E','F','G','H',
                 'I','J','K','L','M','N','O','P','Q',
                 'R','S','T','U','V','W','X','Y','Z'
                };
int strlength,i,j,sum; 
//...................................................................................................................
int main()
{
      SetConsoleOutputCP(1251);
      cout<<"Введите число (меньше 100 цифр): ";
      cin>>ch;
      strlength=strlen(ch);  
      if (strlength>100)                             //проверка на количество цифр в числе  
          {
            cout<<"Число имет больше 100 цифр"<<endl;  
            getch();
            exit(1);
          }
       
      if (strlength%2 != 0)                         
          {
              cout<<"impossible"<<endl<<"Причина: так как количество цифр в числе должно быть парным"<<endl;     
              getch();
              exit(1);
          } 
//...................................................................................................................   
int *mas_ch;
     mas_ch=new (int [strlength]);
        for (j=0;j<strlength;j++)
        for (i=0;i<36;i++)
            if (mas_36[i]==ch[j])
                mas_ch[j]=i;
        for (i=0;i<strlength;i++)
             sum=sum+mas_ch[i];
        if (sum%2 != 0)
    {
        cout<<"impossible"<<endl<<"Причина: так как сумма всех цифр в числе должна быть парной,чтобы была возможность перегруппировать"<<endl;
        getch();
        exit(1);
    }
//...................................................................................................................
int *STEK=new (int [strlength/2]),
    max=0, temp=0, k=1;
        STEK[max]=0;
        if (mas_ch[STEK[max]]>sum/2)
        {
          cout<<"impossible"<<endl<<"Причина:Если одна цифра (в данном случае 1-я) будет строго больше полсуммы числа,то условие задачи не выполнится"<<endl;
          getch();
          exit(1);
        }
    max++;
//...................................................................................................................   
//...................................................................................................................
//...................................................................................................................
while(temp!=sum/2)
                {
                        STEK[max]=k;
                        temp=0;
                        for(i=0; i<=max; i++)
                                temp+=mas_ch[STEK[i]];
                        if(temp>=sum/2 && k<strlength)
                        {
                                k++;
                                max--;
                        }
                        if(temp<sum/2)
                        {
                                if(max==strlength/2)
                                        k++;
                                if(max<strlength/2)
                                {
                                        max++;
                                        k++;
                                }
                        
                        }
                        if(k==strlength+1)
                        {
                                while(STEK[max]-STEK[max-1]==1)
                                        max--;
                                while(STEK[max]-STEK[max-1]!=1)
                                {
                                        max--;
                                        if(max<0)
                                        {
                                                cout<<"impossible\n";
                                                system("pause");
                                                 exit(1);
                                        }
                                }
                                STEK[max]++;
                        }
                        if(STEK[0]==strlength/2)
                        {
                                cout<<"impossible\n";
                                system("pause");
                                exit(1);
                        }
                }
                cout<<"Счастливое число:   ";
                for(i=0;i<strlength/2; i++)
                {
                        cout<<mas_36[mas_ch[STEK[i]]];
                        mas_ch[STEK[i]]=-1;
                }
                for(i=0;i<strlength; i++)
                        if(mas_ch[i]!=-1)
                                cout<<mas_36[mas_ch[i]];
 
                cout<<"\n";
        system("pause");
 
        return 0;
}
Просьба:

Прошу объяснить мне алгоритм выполнение программы,после 3х "комментариев" в виде последовательности точек. По домашней работе задали 40 задач на семестр,эта первая из них.Нашел код в интернете,пытался в нем разобраться,все понял (всмысле проверки) кроме главного,алгоритма перегруппирования цифр. Программа работает не на всех числах (например: 8136 - нормально,а 8631 - не правильно),хочу это исправить,но опять же таки,не знаю как этот код работает на "правильных" числах.На отладку потратил полдня,честно,но ничего так понять и не смог,почему именно берется "strlength/2" и остальное. Кто сможет разобраться и помочь,прошу ответить.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.09.2011, 01:22     Прошу помощи по коду (нужен алгоритм)
Посмотрите здесь:

прошу помощи C++
Прошу коллективной помощи! C++
C++ Списки! Прошу помощи!
Прошу небольшой помощи C++
задачка с матрицами. ПРошу помощи у форума! C++
Прошу помощи ,не двигается змейка C++
C++ прошу помощи, не могу найти ошибку
C++ Помощи прошу

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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