Добре дошли!

Добре дошли в нашите форуми, пълни с полезна информация. Имате проблем с компютъра или телефона си? Публикувайте нова тема и ще намерите решение на всичките си проблеми. Общувайте свободно и открийте безброй нови приятели.

Моля, регистрирайте се за да публикувате тема и да получите пълен достъп до всички функции.

задача за огърлица

Нова тема

23 февруари 20197 г.

Може ли да помогнете с тази задаба: дадена е огърлица от черни и бели мъниста, така че няма две съседни черни мъниста. При зададени w-бели и b-черни мъниста да се отпечатат всички възможни огърлици.

Цитирай

23 февруари 20197 г.

Това цялото условие на задачата ли е? На какъв език трябва да е написана?

Цитирай

23 февруари 20197 г.

Автор

преди 1 минута, badsector написа:

Това цялото условие на задачата ли е? На какъв език трябва да е написана?

това е цялото условие, с++

Цитирай

24 февруари 20197 г.

Един възможен начин е да намериш всички пермутации на мънистата, като за всяка пермутация правиш анализ и дали има съседни черни мъниста. Ако има, изхвърляш пермутацията заедно със всички последващи я пермутации, а ако няма, я отпечатваш...

Понеже това може да е бая дълъг цикъл, първо можеш да направиш анализ дали при съответните бройки черни и бели мъниста задачата въобще има решение. Ако броят на черните мъниста го обозначим Ч, а броят на белите с Б. То при Ч > Б + 1, задачата няма решение. А при Ч = 0 има едно - единствено решение...

...
...
бчбчбч -> валидна пермутация
бччбчб -> невалидна пермутация
бччббч -> пермутацията последваща невалидната пермутация, също се явява невалидна
бчччбб -> пермутацията последваща невалидната пермутация, също се явява невалидна
чбчбчб -> валидна пермутация, тази пермутация не се явява последваща на невалидната пермутация
...
...
...

И всичко това, ако в огърлицата трябва да участват всичките черни и всичките бели мъниста... Иначе, решението се усложнява...

Цитирай

24 февруари 20197 г.

#include <iostream>

using namespace std;

void print(int a[], int n)
{
     static int br=0;
     cout<<++br<<". ";
     for (int i=0; i<n; ++i)
     {
         for (int j=0; j<a[i]; ++j) cout<<"W";
         if (i<n-1) cout<<"B"; else cout<<endl;
     }
}

void shiftarray(int a[], int n, int r)
{
     if (r==0) {print(a,n); return;}
     
     for (int i=0; i<n; ++i)
     {
         ++a[i];
         shiftarray(a,n,r-1);
         --a[i];
     }
}
            
int main()
{
    int b,w,*a;
    cout<<"B = "; cin>>b;
    cout<<"W = "; cin>>w;
    if (b<1 || w<1 || w<b-1) {cout<<"No solution\n"; return 0;}
    a = new int(b+1);
    a[0]=0; a[b]=0;
    for (int i=1; i<b; ++i) a[i]=1;
    shiftarray(a,b+1,w-b+1);
}

Цитирай

24 февруари 20197 г.

Забелязвам един проблем с програмата за който не съм измислил още решение.

Местейки белите топчета може да се получат повтарящи се комбинации образувани с различни бели топчета

Цитирай

25 февруари 20197 г.

За съжалениие нищо умно не можах да измисля по въпроса освен да го направя по най-баламския начин - масив за всички комбинации и изключване на повторенията.

#include <iostream>

using namespace std;

int n, br=0, *a, *c;

void print()
{
     for (int i=0; i<n; ++i) c[br*n+i]=a[i];  
     cout<<++br<<". ";
     for (int i=0; i<n; ++i)
     {
         for (int j=0; j<a[i]; ++j) cout<<"O";
         if (i<n-1) cout<<"+"; else cout<<endl;
     }
}

int check()
{
    for (int i=0; i<br; ++i)
    {
        int j;
        for (j=0; j<n; ++j)
            if (c[i*n+j]!=a[j]) break;
        if (j==n) return 0;
    }   
    return 1;
}    

void shiftarray(int r)
{
     if (r==0) 
     {
          if (check()) print(); 
          return;
     }
     
     for (int i=0; i<n; ++i)
     {
         ++a[i];
         shiftarray(r-1);
         --a[i];
     }
}
            
int main()
{
    int b,w,n2=1;
    cout<<"B = "; cin>>b;
    cout<<"W = "; cin>>w;
    if (b<1 || w<1 || w<b-1) {cout<<"No solution\n"; return 0;}
    n = b+1;
    a = new int[n];
    for (int i=0; i<w-b+1; ++i) n2*=n; 
    c = new int[n2];
    a[0]=0; a[b]=0;
    for (int i=1; i<b; ++i) a[i]=1;
    shiftarray(w-b+1);
}

Цитирай

25 февруари 20197 г.

6-ти ред отзад напред да се коригира на

for (int i=0; i<w-b+2; ++i) n2*=n;

че неправилно се определя размера на масива в който се записват готовите комбинации

Цитирай

28 февруари 20197 г.

на ‎23‎.‎2‎.‎2019‎ г. в 19:36, Plamy Gerova написа:

Може ли да помогнете с тази задаба: дадена е огърлица от черни и бели мъниста, така че няма две съседни черни мъниста. При зададени w-бели и b-черни мъниста да се отпечатат всички възможни огърлици.

Ето ти едно кратко решение с STL

#include <iostream>
#include <string>
#include <algorithm>

int main()
{
	int black, white;
	std::cout << "Enter the number of BLACK beads: ";
	std::cin >> black;
	std::cout << "Enter the number of WHITE beads: ";
	std::cin >> white;
	
	std::string necklace(black, 'B');
	necklace.append(white, 'W');

	do
	{
		if (necklace.find("BB") == std::string::npos)
			std::cout << necklace << std::endl;
	} while (next_permutation(necklace.begin(), necklace.end()));

	return 0;
}

Цитирай

4 седмици по-късно...

27 март 20197 г.

Автор

Благодаря много за задачката оценявам помощта, бях се отчаяла с нея и чак днес проверих форума 😊😅

на 28.02.2019 г. в 22:50, barry написа:

Ето ти едно кратко решение с STL


#include <iostream>
#include <string>
#include <algorithm>

int main()
{
	int black, white;
	std::cout << "Enter the number of BLACK beads: ";
	std::cin >> black;
	std::cout << "Enter the number of WHITE beads: ";
	std::cin >> white;
	
	std::string necklace(black, 'B');
	necklace.append(white, 'W');

	do
	{
		if (necklace.find("BB") == std::string::npos)
			std::cout << necklace << std::endl;
	} while (next_permutation(necklace.begin(), necklace.end()));

	return 0;
}

на 25.02.2019 г. в 21:49, ined написа:
6-ти ред отзад напред да се коригира на
for (int i=0; i<w-b+2; ++i) n2*=n;
че неправилно се определя размера на масива в който се записват готовите комбинации

Благодаря много

Цитирай

28 март 20197 г.

Чак сега е дошло времето да се предава задачата и затва чак сега проверяваш иначе направо ги беше отебала

Цитирай

petie1

Лига на легендите

Пол:Мъж
Град:Марс Сити
Интереси:Линукс и Програмиране да се правя на луд научна фанстастика шеги книги за компютри и програмиране

28 март 20197 г.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
  
int main()
{
	int black, white;
	cout << "Enter the number of BLACK beads: ";
	cin >> black;
	cout << "Enter the number of WHITE beads: ";
	cin >> white;
	
	string necklace(black, 'B');
	necklace.append(white, 'W');

	do
	{
		if (necklace.find("BB") == string::npos)
			cout << necklace << endl;
	} while (next_permutation(necklace.begin(), necklace.end()));

	return 0;
}

Така ми се вижда по добре кода

Цитирай

29 март 20197 г.

Кода е супер, ама обикновенно даскалите в подобни задачи не дават да се ползва STL ами учениците сами да си напишат функциите

Цитирай

29 март 20197 г.

using namespace std се счита за лош

преди 16 часа, petie1 написа:


#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
  
int main()
{
	int black, white;
	cout << "Enter the number of BLACK beads: ";
	cin >> black;
	cout << "Enter the number of WHITE beads: ";
	cin >> white;
	
	string necklace(black, 'B');
	necklace.append(white, 'W');

	do
	{
		if (necklace.find("BB") == string::npos)
			cout << necklace << endl;
	} while (next_permutation(necklace.begin(), necklace.end()));

	return 0;
}

Така ми се вижда по добре кода

using namespace std се счита за лоша практика и в много случаи префикса прави кода по-лесно четим и разбираем

Цитирай

Архивирана тема

Темата е твърде стара и е архивирана. Не можете да добавяте нови отговори в нея, но винаги можете да публикувате нова тема, в която да продължи дискусията. Регистрирайте се или влезте във вашия профил за да публикувате нова тема.