Регистрация не е нужна, освен при създаване на тема в "Задача на седмицата".

Рекурсия C++

Рекурсия C++

Мнениеот Гост » 05 Мар 2018, 14:11

Моля помогнете! Трябва да направя анализ на следния код на следната задача:
Да се състави програма, която извежда всички комбинации от по R-цифрени числа от N-цифри. Например, при N=3 и R=2 комбинациите са 12,13,21,23,31,32. Тоест да ми изведе двуцифрени числа с цифрите от 1 до 3. ето го и кода:
#include <iostream>
using namespace std;
const int MAXN=20;


int n,r;

char a[MAXN]={0};
int dancho[MAXN];

void function(int i);
void print();



void function(int i)
{
int k;
if(i >= r)
{
print();
return;
}

for(k=0;k<n;k++)
{
if(!a[k])
{
a[k]=1;
dancho[i]=k;
function(i+1);
a[k]=0;
}
}
}

void print()
{
int i;
for(i=0;i<r;i++)
{
cout<<dancho[i]+1;
}
cout<<endl;
}

void main()
{
cout<<"vuvedte r";
cin>>r;
cout<<"vuvedte n";
cin>>n;
function(0);
}

Ако някой може да ми обясни горе долу всеки ред за какво е с 2-3 думички за ред ще съм много благодарен :)
Гост
 

Re: рекурсия

Мнениеот Davids » 06 Мар 2018, 02:15

В тоя код са нарушени сума конвенции на етичното писане на код :lol: Да не казвам, че прилича сякаш някой си е правил гавра с теб. Но със сигурност не бих го приел, ако бях професор. Ще се огранича до основните забележки:
1) имената на променливите са като извадени от графата "абсолютно табу - не правете така" на някой учебник;
2) идентация липсва, както и разумна подреденост на кода (но да речем, че последното е по-скоро вкусова преференция)
3) кодът е изключително неприятен за проследяване в този си вид, което вероятно причинява и затрудняванията ти.
Можеше в един [code] таг да го сложиш, ама айде. Ще се опитам да ти олесня живота с нещо по-четливо, макар и с C++ да сме скарани отдавна... :lol:
Допускам, че повторение на цифри не е възможно и нулата не участва (тъй като входът ни е по-голям от нула).

За мен нещо такова би било оптимално като алгоритъм, разбира се, се допускат леки изменения, като например начинът на пренос на вече обходените цифри (избрал съм string малко против конвенцията, но с оглед на оптималната употреба на памет), но идеята остава същата: Взимаме и валидираме входа, като са ни нужни две цифри от 1 до 9, като, разбира се, $r < n$, защото не можем да имаме например 5 цифрено число от 4 цифри без повторение. Започваме итерация, като обхождаме $r$ пъти всяка от цифрите от 1 до $n$ и добавяме към преносителя на вече обходената информация - string-ът $previous$. С негова помощ проверяваме и при всяка следваща итерация дали цифрата вече не се съдържа в нашето число. Другият ключов параметър на итериращата функция $loopDigits$ е и броят на оставащите цифри докрая - в началото стартираме с $r$ оставащи нужни цифри и след всяка добавена цифра инициираме същата функция, но вече с една цифра по-малко като брой. И така докато оставащата цифра не остане една (клаузата $digitsCount == 1$), което означава, че след като е преминала първата проверка, то тя е валидна цифра (т.е. не се съдържа) и можем вече да принтираме число - т.е. принтираме събраните досега цифри и накрая текущата, след което преминаваме към следващата в loop-а. Това е. Ако има нещо неясно, питай. Оставял съм бележки и по кода... Трябва да ти кажа обаче, че с $C++$ нещо хич не се харесваме и има възможност да не съм подбрал оптимален синтаксис или набор от способи (там можеш да си доразвиваш, ако имаш желание), но важна е идеята.

П.С.: Има го и естествено другия подход, където още първоначално си създаваме един едномерен integer масив с големина $n$ елемента и го пълним с всички цифри като $char$-ове и накрая пишем един итерационен алгоритъм на принципа "всяко с всички останали във всеки възможен ред", но е излишно играчка според мен, при положение че може да се изпипа и на по-функционален принцип отколкото обектен :P

П.П.С.: system("pause") съм го добавил, за да е нагледен резултатът, принципно не е препоръчително, тъй като е чисто windows related трикче за паузиране на конзолата. Ако ще искаш да дебъгваш на друг OS, ще трябва да си сложиш я breakpoint, я някое изчакване за вход. Но там би трябвало да си наясно :lol:
*Нещо непосредствено и интересно, привличащо вниманието на читателя и оставящо го с приятна топла усмивка на лицето.*
----
Вече не го правя само за точката. :lol:
Davids
Математик
 
Мнения: 2394
Регистриран на: 16 Ное 2015, 11:47
Рейтинг: 2552

Re: Рекурсия C++

Мнениеот Гост » 06 Мар 2018, 17:02

искам само да попитам на този код, който ти си предложил къде точно е рекурсията и също как точно ще се измени кода ако може да има повторения на цифрите и също да има и 0 ?
Гост
 

Re: Рекурсия C++

Мнениеот Davids » 06 Мар 2018, 17:16

Гост написа:искам само да попитам на този код, който ти си предложил къде точно е рекурсията и също как точно ще се измени кода ако може да има повторения на цифрите и също да има и 0 ?

Свел съм кода до няколко, броящи се на пръсти, функционални реда - рекурсуята, смятам, се забелязва лесно. Знаеш ли какво представлява тя въобще и къде да я търсиш? Тя се случва там, където викаш даден метод от самото му тяло (в случая - loopDigits функцията).
А за другите въпроси отговорът е лесен - за да включим повторението на цифри, трябва просто са се премахне проверката за еднаквост; а за да включим нулата, трябва просто да започнем итерацията от 0, а не от 1, и да включим проверка, която да изключва случая, в който 0 е в началото на числото. Това е.
*Нещо непосредствено и интересно, привличащо вниманието на читателя и оставящо го с приятна топла усмивка на лицето.*
----
Вече не го правя само за точката. :lol:
Davids
Математик
 
Мнения: 2394
Регистриран на: 16 Ное 2015, 11:47
Рейтинг: 2552


Назад към C, C++



Кой е на линия

Регистрирани потребители: Google [Bot]

Форум за математика(архив)