@kachailov

С++ — как решить задачку про «Болты и Гайки»?

Привет, хабр. Дали мне решить задачу. Мозг уже просто разрывается, так что спасайте

Есть два массива по, к примеру, 5 элементов. Массив "Болтов" и массив "Гаек", каждый Болт отличается размером и к каждому из них есть соответствующая гайка из другого массива.

Нужно отсортировать оба массива по возрастанию, при этом нельзя сравнивать размер болта с другим болтом и размер гайки с другой гайкой. Единственное, что можно сравнивать, это размер болта и размер гайки. Соответственно, есть только 3 состояния: 1. Гайка меньше болта. 2. Гайка подходит к болту. 3. Гайка слишком большая

Вот что есть:

#include <iostream>
#include <string>
using namespace std;

int const SIZE = 5;

class BoltsAndScrews
{

public:
	BoltsAndScrews();
	
	void DisplayBolts();
	void DisplaySmallBolts();
	void DisplayBigBolts();

	void DisplayScrews();
	void DispalyBigScrews();
	

	void addBolt(int);
	void addScrew(int);

	void findMAX();

private:
	int numberOfScrews = 0;
	int numberOfBolts = 0;

	int counter1 = 0;
	int counter2 = 0;
	int max;



	int arrayOfBolts[SIZE];
	int arrayOfScrews[SIZE];

	int arrayOfBigBolts[SIZE];
	int arrayOfSmallBolts[SIZE];

	int arrayOfBigScrews[SIZE];
	int arrayOfSmallScrews[SIZE];
	
	int arrayOfPairs[SIZE];


	

};

BoltsAndScrews::BoltsAndScrews()
{
	
}

int main()
{


	BoltsAndScrews test1;

	test1.addBolt(1);
	test1.addBolt(2);
	test1.addBolt(3);
	test1.addBolt(4);
	test1.addBolt(5);

	test1.addScrew(5);
	test1.addScrew(4);
	test1.addScrew(3);
	test1.addScrew(2);
	test1.addScrew(1);

	cout << endl;
	test1.DisplayBolts();
	test1.DisplayScrews();
	cout << endl;
	test1.findMAX();
	cout << endl << endl;

	test1.DispalyBigScrews();
	cout << endl;
	test1.DisplayBigBolts();

	cin.get();
	cin.get();
	return 0;
}

void BoltsAndScrews::DisplayBolts()
{
	cout << "Array Of  Bolts: ";
	for (int i = 0; i < SIZE; i++)
	{
		cout << arrayOfBolts[i] << " ";
	}
	cout << endl;
}

void BoltsAndScrews::DisplayScrews()
{
	cout << "Array Of Screws: ";
	for (int i = 0; i < SIZE; i++)
	{
		cout << arrayOfScrews[i] << " ";
	}
	cout << endl;
}


void BoltsAndScrews::DispalyBigScrews()
{
	cout << "Array Of BIG Screws ";
	for (int i = 0; i < SIZE; i++)
	{
		cout << arrayOfBigScrews[i] << " ";
	}
	cout << endl;
}

void BoltsAndScrews::DisplayBigBolts()
{
	cout << "Array Of BIG Bolts: ";
	for (int i = 0; i < SIZE; i++)
	{
		cout << arrayOfBigBolts[i] << " ";
	}
	cout << endl;
}

void BoltsAndScrews::addBolt(int x) 
{
	arrayOfBolts[numberOfBolts] = x;
	numberOfBolts++;
}

void BoltsAndScrews::addScrew(int x)
{
	arrayOfScrews[numberOfScrews] = x;
	numberOfScrews++;
}

void BoltsAndScrews::findMAX()
{
	
	for (int i = 0; i < SIZE; i++) //pick fist bolt
	{
		for (int j = 0; j < SIZE; j++) //pick the first scew and compaire it to bolt below. If not math, pick next screw and so on
		{
			if (arrayOfBolts[i] < arrayOfScrews[j])
			{
				cout << "Condition: Screw will go in the bolt." << " Bolt: [" << arrayOfBolts[i] << "] less than Screw: [" << arrayOfScrews[j] <<"]"<< endl;
				
				
		
			}
			
			if (arrayOfBolts[i] == arrayOfScrews[j])
			{
				cout << endl << "Condition: Screw will fit bolt exactly." << " Bolt: [" << arrayOfBolts[i] << "] same as Screw: [" << arrayOfScrews[j] << "]" << endl << endl;
			
				

			}
			
			if (arrayOfBolts[i] > arrayOfScrews[j])
			{
				cout << "Condition: Screw will be loose." << " Bolt: [" << arrayOfBolts[i] << "] bigger than Screw: [" << arrayOfScrews[j] <<"]"<< endl;
				
				
			}
			
			
			
		} // Screw
	
		

	
	} // bolt
}
  • Вопрос задан
  • 5567 просмотров
Решения вопроса 1
FirstX
@FirstX
.net developer
Самое интересное, я Вам изначально писал про сложность и даже давал ответ) Смотрите сами: получение пар - сложность квадратичная, потом сортировка вставками (если тот код использовали, что я вам давал) - тоже квадратичная сортировка. Итого 2 * n^2, но 2ка это константа, а при верхней оценке константы не учитываются, поэтому сложность всего алгоритма тоже квадратичная получается.
Ответ написан
Пригласить эксперта
Ответы на вопрос 7
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Задача лёгкая, но... это же Вас интервьюируют, а не коллективный интернет-разум.
Ответ написан
@Skver0
с++ не знаю но возможно вам поможет код на питоне.
bolts = (4, 3, 2, 1, 5)
gaiki = (1, 2, 3, 4, 5)

sp = [] # тут будет список списков

for bolt in bolts:
    for gaika in gaiki:
        if gaika == bolt:
            sp.append([gaika, bolt]) # добавляем пары в список sp

print(sp)

n = 1
while n < len(sp): # пузырьковая сортировка.
    for i in range(len(sp)-n):
        if sp[i][0] > sp[i+1][1]:  # сравниваем болт и гайку.
            sp[i],sp[i+1] = sp[i+1],sp[i]
    n += 1
print(sp)
Ответ написан
FirstX
@FirstX
.net developer
Код не смотрел, но если правильно понял условие, то нужно обойти в цикле каждый болт и посчитать, сколько для каждого болта есть гаек, у которых размер меньше.

Описываю случай, когда подразумевается, что все размеры уникальны. Для не уникальных придется идею чуть модифицировать.

Например болты А = { 2, 3, 7, 5, 4 } и гайки B = { 3, 7, 2, 4, 5 }

Берем первый болт А0 = 2. Сравнивая с гайками, получаем, что гаек, которых меньше, чем А0 ноль. Это и будет позиция (нулевая) А0 в отсортированном массиве. Тут же кстати можно найти при обходе и тот случай, где они равны (B2) - и B2 ставим тоже в нулевую позицию. (Если можно использовать доп. массив то просто формируем вставляя данные в нужные позиции, если нет - то меняем местами элементы в существующем)

Берем второй болт A1 = 3. Кол-во меньших гаек - 1. Значит A1 так и остается в A1. Попутно нашли B0, которым ставим в позицию B1.

Третий болт A2 = 7. Кол-во меньших гаек - 4. Значит A2 ставим в A4. Находим равную гайку - B1 и ставим ее тоже с индексом 4, то есть в B4. И так далее до конца. Получаем 2 отсортированных массива по возрастанию.

Правда получается, что сложность квадратичная, будет время постараюсь подумать над этим. Если что-то не так понял из условия, то уточните как раз.
Ответ написан
@Skver0
с++ я не знаю но чето типа того....

for(x=0;x<size-1;x++)
for(y=x+1;y<size;++y)
if (array1[x]>array2[y])
{
    temp=array1[x];
    array1[x]=array1[y];
    array1[y]=temp;
    temp=array2[x];
    array2[x]=array2[y];
    array2[y]=temp;
}
Ответ написан
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Algorithmic complexity - верхняя оценка сложности алгоритма. Например, оценка O(n) означает, что сложность линейная, то есть в простом случае проход по массиву осуществляется один раз; O(n2) - квадратичная, для каждого элемента массива проводится сравнение с каждым; Пузырьковая сортировка имеет оценку O(n*log(n)). Коротко почитать можно здесь
Ответ написан
@kachailov Автор вопроса
Пришел к этапу когда у меня есть два иднетичных массива, которые представляют собой пару ( болт + гайка ) Ex. arrayOfScrews[0] = arrayOfBolts[0], arrayOfScrews[1] = arrayOfScrews[1] и так далее.

Теперь в моей голове сложилась картина, что нужно сравнивать между собой, но не болт со следующим болтом, а болт со следующей гайкой, она ведь по размеру следующего болта.

Люди добрые, кто может написать такую функцию? Голова уже совсем не варит

Вот код:

#include <iostream>
#include <string>

using namespace std;

int const SIZE = 5;
int const SIZE2 = 2;
int const SIZE3 = 5;

class BoltsAndScrews
{

public:
	BoltsAndScrews();

	void DisplayBolts();
	void DisplayScrews();

	void DisplayArrayOfPairs();

	void addBolt(int);
	void addScrew(int);

	void findPairs();
	void fillOut2Darray(int, int);

	void Sort();


private:
	int numberOfScrews = 0;
	int numberOfBolts = 0;

	int counter1 = 0;
	int counter2 = 0;
	int max;

	int BoltsByMax[SIZE];
	int ScrewsByMax[SIZE];

	int arrayOfBolts[SIZE];
	int newArrayOfBolts[SIZE];
	int arrayOfScrews[SIZE];
	int newArrayOfScrews[SIZE];


	int arrayOfPairs[SIZE2][SIZE3];

};

BoltsAndScrews::BoltsAndScrews()
{

}

int main()
{


	BoltsAndScrews test1;

	test1.addBolt(1);
	test1.addBolt(2);
	test1.addBolt(3);
	test1.addBolt(4);
	test1.addBolt(5);

	test1.addScrew(5);
	test1.addScrew(4);
	test1.addScrew(3);
	test1.addScrew(2);
	test1.addScrew(1);

	cout << endl;
	test1.DisplayBolts();
	test1.DisplayScrews();
	cout << endl;
	test1.findPairs();
	cout << endl << endl;



	test1.DisplayArrayOfPairs();
	cout << endl << endl;
	test1.Sort();

	cin.get();
	cin.get();
	return 0;
}

void BoltsAndScrews::DisplayBolts()
{
	cout << "Array Of  Bolts: ";
	for (int i = 0; i < SIZE; i++)
	{
		cout << arrayOfBolts[i] << " ";
	}
	cout << endl;
}

void BoltsAndScrews::DisplayScrews()
{
	cout << "Array Of Screws: ";
	for (int i = 0; i < SIZE; i++)
	{
		cout << arrayOfScrews[i] << " ";
	}
	cout << endl;
}


void BoltsAndScrews::DisplayArrayOfPairs()
{
	cout << "Array Of Pairs: " << endl;

	for (int j = 0; j < 5; j++)
	{
		cout << newArrayOfBolts[j] << " ";
	}

	cout << endl;

	for (int i = 0; i < 5; i++)
	{
		cout << newArrayOfScrews[i] << " ";
	}
	cout << endl;


}
void BoltsAndScrews::addBolt(int x)
{
	arrayOfBolts[numberOfBolts] = x;
	numberOfBolts++;
}

void BoltsAndScrews::addScrew(int x)
{
	arrayOfScrews[numberOfScrews] = x;
	numberOfScrews++;
}

void BoltsAndScrews::fillOut2Darray(int x, int y)
{


	int bolt = x;
	int screw = y;

	newArrayOfBolts[counter1] = bolt;
	newArrayOfScrews[counter2] = screw;

	counter1++;
	counter2++;

	cout << "FillOutThing - " << bolt << " " << screw << endl << endl;

	return;

}

void BoltsAndScrews::Sort()
{
	

	int index = 0;
	int count1 = 0, count2 = 0;;
	
	do
	{
		
		for (int i = 0; i < SIZE; i++)
		{
			if (newArrayOfBolts[i] >= newArrayOfScrews[i])
			{
				cout << newArrayOfBolts[i] << " = " << newArrayOfScrews[i] << endl;
				
				BoltsByMax[count1] = newArrayOfBolts[i];
				ScrewsByMax[count2] = newArrayOfScrews[i];
				index = i;
			}

		}



		count1++;
		count2++;
		index++;

		cout << endl << "Bolts By Max: ";
		for (int i = 0; i < SIZE; i++)
		{
			cout << BoltsByMax[i];
		}

		cout << endl << "Screws By Max: ";
		for (int i = 0; i < SIZE; i++)
		{
			cout << ScrewsByMax[i];
		}

	} while (index > SIZE);
		
	
		
}

void BoltsAndScrews::findPairs()
{

	for (int i = 0; i < SIZE; i++) //pick fist bolt
	{
		for (int j = 0; j < SIZE; j++) //pick the first scew and compaire it to bolt below. If not math, pick next screw and so on
		{
			if (arrayOfBolts[i] < arrayOfScrews[j])
			{
				cout << "Condition: Screw will go in the bolt." << " Bolt: [" << arrayOfBolts[i] << "] less than Screw: [" << arrayOfScrews[j] << "]" << endl;
			}

			if (arrayOfBolts[i] == arrayOfScrews[j])
			{
				cout << endl << "Condition: Screw will fit bolt exactly." << " Bolt: [" << arrayOfBolts[i] << "] same as Screw: [" << arrayOfScrews[j] << "]" << endl << endl;

				cout << endl << "bolt " << arrayOfBolts[i];
				cout << endl << "screw " << arrayOfScrews[j] << endl << endl;;

				newArrayOfBolts[counter1] = arrayOfBolts[i];
				newArrayOfScrews[counter2] = arrayOfScrews[j];
				counter1++;
				counter2++;

				/*fillOut2Darray(arrayOfBolts[i], arrayOfScrews[j]);*/

			}

			if (arrayOfBolts[i] > arrayOfScrews[j])
			{
				cout << "Condition: Screw will be loose." << " Bolt: [" << arrayOfBolts[i] << "] bigger than Screw: [" << arrayOfScrews[j] << "]" << endl;
			}


		} // Screw

	} // bolt

}


Собственно интересующая меня функиция - Sort()
Ответ написан
Комментировать
@kachailov Автор вопроса
Ребята, спасибо за помощь! Таки домучал я эту задачу.

Повилась следующая проблема. По этому алгоритму теперь меня завалили вопросом " please provide the algorithmic complexity of your algorithm in Big O notation as well"

Понятия не имею что это такое) Может кто-то с таким сталкивался ?
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы