Главная Вход в систему Регистрация
Задать вопрос Консультации Пользователи Форум
О системе Помощь
Задать вопрос экспертам
Консультация № 196608
08.10.2019, 15:34
0.00 руб.
0 11 2
Компьютеры Программирование
Уважаемые эксперты! Пожалуйста, ответьте на вопрос:

Напишите эффективную программу, находящуюи выводящую на экран все числа длины n являющиеся палиндромами.
Понятно, что для четного n нужно записать все расстановки цифр 1..9 в количестве от 1 до n/2 (для нечетного до (n-1)/2), а потом их продублировать в обратном порядке, но как сделать эту программу наиболее эффективной?

Заранее спасибо.

Обсуждение

давно
Лысков Игорь Витальевич
Посетитель
7438
7205
08.10.2019, 16:20
общий
Адресаты:
но как сделать эту программу наиболее эффективной?
Так понимаю, менее эффективная, на Ваш взгляд, программа имеется...
Почему бы Вам ее не привести? Посмотрим, вместе оптимизируем...
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
давно
Хватов Сергей
Академик
20764
1861
08.10.2019, 17:52
общий
Вывести на экран — это к C/C++ прямого отношения не имеет. Совсем. Платформу озвучьте
И уточните как числа могут быть палиндромами. Из совсем разных разделов термины.
давно
Gluck
Студент
402651
154
08.10.2019, 22:36
общий
это ответ
Здравствуйте, moonfox!
Вот код только для чисел...

// Проверка введеного числа на полиндром
#include <cstdlib>
#include <iostream>

using namespace std;

int isPal(int n)
{
int p,k,m;
k=0;
m=n;
while(m > 0)
{
p=m % 10;
m=m/10;
k=k*10+p;
}
return (n==k);
}

int main(int argc, char *argv[])
{
int n;
cout << "n=";
cin >> n;
isPal(n)?cout << "yes":cout << "no";
cout << endl;

system("PAUSE");
return EXIT_SUCCESS;
}

Сл-щие для символов, т.е. как для чисел, так и слов...

1.
// Проверка введеных символов на полиндром
#include <iostream>
#include <algorithm>
#include <string>
#include <locale>

using namespace std;
bool is_Palindrome(const string& w)
{
return equal(w.begin(), w.end(), w.rbegin());
}

int main()
{
setlocale(LC_ALL,"Russian");
cout << "введите число (или слово)" << endl;
string w;
cin >> w;
if(is_Palindrome(w))
cout << w << " - палиндром";
else
cout << w << " - не палиндром";
system("PAUSE");
return 0;
}

2.
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <locale>
using namespace std;

bool check_polindrom(string word)
{
int len = word.length();
for(int i = 0; i < len/2; ++i)
{
if(word[i] != word[len-i-1])
{
return false;
}
}
return true;
}

int main()
{
setlocale(LC_ALL,"Russian");
string str;
cout << "введите число (или слово)";
cin >> str;
if(check_polindrom(str))
{
cout << str << " - палиндром." << endl;
}
else
{
cout << str << " - не палиндром" << endl;
}
system("PAUSE");
return 0;
}
А, какой из них более рациональный или "наиболее эффективный?" решай сам или кто там...
3
Спасибо конечно, но нужно было вывести все палиндромы длиной n, а не проверять, является ли n палиндромом или нет.
давно
moonfox
Посетитель
400539
9
08.10.2019, 23:21
общий
Цитата: Лысков Игорь Витальевич
Так понимаю, менее эффективная, на Ваш взгляд, программа имеется...

Если бы имелась, я бы сам ее оптимизировал)
Есть просто идея для алгоритма решения, но все же хотелось бы по возможности увидеть другие варианты решения.
давно
Лысков Игорь Витальевич
Посетитель
7438
7205
08.10.2019, 23:30
общий
Адресаты:
Идея алгоритма - тоже неплохо...
Алгоритм - это основа программы.
Так что, рассказывайте, не стесняйтесь...
Будет необходимость, будем искать "другие варианты решения".
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
давно
Хватов Сергей
Академик
20764
1861
09.10.2019, 01:18
общий
И я и Игорь Витальевич много чего можем придумать. Только ваш препер с первового же байта поймёт, что вы это сделали не сами. И задаст маааленький доп вопрос. После чего вы на нас же будете обижаться.
давно
moonfox
Посетитель
400539
9
09.10.2019, 23:35
общий
10.10.2019, 00:43
Цитата: Лысков Игорь Витальевич
Идея алгоритма - тоже неплохо

Хорошо.

Создаем массив из n переменных и присваиваем им всем значение 0.
Затем прибавляем по единице с противоположных концов с индексами i и (n-i+1)
Допустим, было 0 0 0 0 0-> 1 0 0 0 1-> 1 1 0 1 1 -> ... -> 2 1 1 1 2 -> 2 2 1 2 2 -> ... -> 9 9 8 9 9 -> 9 9 9 9 9
Каждый раз выводим получившийся палиндром то тех пор, пока a[i] не привышает 9
давно
Лысков Игорь Витальевич
Посетитель
7438
7205
10.10.2019, 10:47
общий
Адресаты:
неплохо, но полагаю, что все варианты мы не получим.
Например, 14341
Кроме того, надо учитывать повторяющиеся цифры.
Ещё будут мысли?
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
давно
moonfox
Посетитель
400539
9
10.10.2019, 20:59
общий
Цитата: Лысков Игорь Витальевич
все варианты мы не получим

да, проблема...

Цитата: Лысков Игорь Витальевич
Ещё будут мысли?

дельных - нет
давно
Зенченко Константин Николаевич
Старший Модератор
31795
6196
11.10.2019, 12:14
общий
11.10.2019, 12:14
Адресаты:
Вот на паскале накидал:
[code lang=pascal]const
n=10;
m=5;
a:array[0..n]of string[2]=(('0'),('1'),('2'),('3'),('4'),('5'),('6'),('7'),('8'),('9'),(''));
var
b:array[1..m]of byte;
c,d,e,f:integer;
begin
b[1]:=0;
e:=0;
repeat
d:=1;
c:=0;
repeat
inc(b[d]);
c:=b[d]div n;
b[d]:=b[d]mod n;
d:=d+c;
if e<d then e:=d;
until(c=0)or(d>m);
if d<=m then
begin
writeln('out:');
f:=n;
repeat
for c:=e downto 1 do write(a[b[c]]);
write(a[f]);
f:=f mod n;
for c:=1 to e do write(a[b[c]]);
writeln;
inc(f);
until f=n;
readln;
end;
until d>m;
end.[/code]

Получается такое:
[code h=200]out:
11
111
121
131
141
151
161
171
181
191
out:
22
212
222
232
242
252
262
272
282
292
out:
33
313
323
333
343
353
363
373
383
393
out:
44
414
424
434
444
454
464
474
484
494
out:
55
515
525
535
545
555
565
575
585
595
out:
66
616
626
636
646
656
666
676
686
696
out:
77
717
727
737
747
757
767
777
787
797
out:
88
818
828
838
848
858
868
878
888
898
out:
99
919
929
939
949
959
969
979
989
999
out:
1001
10101
10201
10301
10401
10501
10601
10701
10801
10901
out:
1111
11111
11211
11311
11411
11511
11611
11711
11811
11911
out:
1221
12121
12221
12321
12421
12521
12621
12721
12821
12921
out:
1331
13131
13231
13331
13431
13531
13631
13731
13831
13931
out:
1441
14141
14241
14341
14441
14541
14641
14741
14841
14941
out:
1551
15151
15251
15351
15451
15551
15651
15751
15851
15951
out:
1661
16161
16261
16361
16461
16561
16661
16761
16861
16961
out:
1771
17171
17271
17371
17471
17571
17671
17771
17871
17971
out:
1881
18181
18281
18381
18481
18581
18681
18781
18881
18981
out:
1991
19191
19291
19391
19491
19591
19691
19791
19891
19991
out:
2002
20102
20202
20302
20402
20502
20602
20702
20802
20902
out:
2112
21112
21212
21312
21412
21512
21612
21712
21812
21912
out:
2222
22122
22222
22322
22422
22522
22622
22722
22822
22922
out:
2332
23132
23232
23332
23432
23532
23632
23732
23832
23932
out:
2442
24142
24242
24342
24442
24542
24642
24742
24842
24942
out:
2552
25152
25252
25352
25452
25552
25652
25752
25852
25952
out:
2662
26162
26262
26362
26462
26562
26662
26762
26862
26962
out:
2772
27172
27272
27372
27472
27572
27672
27772
27872
27972
out:
2882
28182
28282
28382
28482
28582
28682
28782
28882
28982
out:
2992
29192
29292
29392
29492
29592
29692
29792
29892
29992
out:
3003
30103
30203
30303
30403
30503
30603
30703
30803
30903
out:
3113
31113
31213
31313
31413
31513
31613
31713
31813
31913
out:
3223
32123
32223
32323
32423
32523
32623
32723
32823
32923
out:
3333
33133
33233
33333
33433
33533
33633
33733
33833
33933
out:
3443
34143
34243
34343
34443
34543
34643
34743
34843
34943
out:
3553
35153
35253
35353
35453
35553
35653
35753
35853
35953
out:
3663
36163
36263
36363
36463
36563
36663
36763
36863
36963
out:
3773
37173
37273
37373
37473
37573
37673
37773
37873
37973
out:
3883
38183
38283
38383
38483
38583
38683
38783
38883
38983
out:
3993
39193
39293
39393
39493
39593
39693
39793
39893
39993[/code]
Блок схема на рисунке, времени переводить на С нет. Захочите переведете.
Прикрепленные файлы:
6d33135c414066a648a741b1a3f52f6e.bmp
скачать (1.18 МБ)
Об авторе:
Мне безразлично, что Вы думаете о обо мне, но я рад за Вас - Вы начали думать.

давно
Лысков Игорь Витальевич
Посетитель
7438
7205
11.10.2019, 15:27
общий
это ответ
Здравствуйте, moonfox!
Держите решение...
Идея: перебираем ВСЕ цифры первой половины, затем выводим сначала первую половину, затем вторую.
Учитывается четное/нечетное количество цифр
Для перебора всех цифр использован рекурсивный вызов получения очередной цифры.
Для хранения очередных цифр использован массив из 100 значений, т.е. нельзя искать полиндромы более 201 цифры
Этот момент легко меняется: зная n, можно получить требуемый массив динамически... Программа демонстрирует идею...
Рекомендую изучить код, чтобы понять, как можно организовать неизвестное заранее количество вложенных циклов...
Код:
#include <iostream>
using namespace std;

int ind[100];	//здесь будем хранить цифры, ограничимся числами до 201 цифр

void palindrom(int n, int t) //n - всего цифр, t - позиция формирования
{
	int m = (n >> 1) + (n & 1); //количество цифр слева. Для нечетного - включаем и центральную

	if (t == m)	//полный набор?
	{
		if (ind[0] != 0)	//первые нули игнорируем
		{
			for (int i = 0; i < m; i++)	//левая половина
				cout << ind[i] << " ";
			for (int i = (n & 1) ? m - 2 : m - 1; i >= 0; i--) //правая половина
				cout << ind[i] << " ";
			cout << endl;
		}
		return;
	}
	for (int i = 0; i < 10; i++)	//перебираем цифры
	{
		ind[t] = i;					//на t позиции
		palindrom(n, t + 1);		//форируем рекурсивно дальше!
	}
}

int main() {
	int n;		//общее число цифр
	cin >> n;
	palindrom(n, 0);
	system("pause");
	return 0;
}


Небольшая модификация программки:
Код:
#include <iostream>
using namespace std;

int *ind = NULL;	//здесь будем хранить цифры
int m;
int r;

void palindrom(int t) //t - позиция формирования
{
	if (t == m)	//полный набор?
	{
		if (ind[0] != 0)	//первые нули игнорируем
		{
			for (int i = 0; i < m; i++)	//левая половина
				cout << ind[i] << " ";
			for (int i = r ; i >= 0; i--) //правая половина
				cout << ind[i] << " ";
			cout << endl;
		}
		return;
	}
	for (int i = 0; i < 10; i++)	//перебираем цифры
	{
		ind[t] = i;					//на t позиции
		palindrom(t + 1);		//форируем рекурсивно дальше!
	}
}

int main() {
	int n;		//общее число цифр
	cin >> n;
	m = (n >> 1) + (n & 1); //количество цифр слева. Для нечетного - включаем и центральную
	r = (n & 1) ? m - 2 : m - 1;
	ind = new int[m];
	palindrom(0);
	delete[] ind;
	system("pause");
	return 0;
}
Об авторе:
"Если вы заметили, что вы на стороне большинства, —
это верный признак того, что пора меняться." Марк Твен
Форма ответа