Я хочу решить проблему с алгоритмом.
Не могли бы вы предложить какие-нибудь алгоритмы, работающие быстрее?
* Краткое описание проблемы
- Найти тот же массив ключей [200], что и исходный массив KEY [200]
- Каждый элемент массива KEY [200] имеет диапазон случайных чисел 1 ~ 255.
- дается только 2 файла.
- Вы должны реализовать только функцию find_array () из user_code.cpp
- Не разрешено редактировать любые другие вещи
- Вы можете использовать функцию check () для поиска массива
- тестовый случай 50, ограничение времени 10 секунд для 50 тестов, ограничение памяти 256 МБ.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
extern void find_array(unsigned char key[200]);
unsigned char KEY[200];
int check(unsigned char key[200])
{
int pos = 0;
int equal = 0;
for (int c = 0; c < 200; c++)
{
if (key[c] == KEY[c])
pos++;
}
for (int c1 = 0; c1 < 200; c1++)
{
for (int c2 = 0; c2 < 200; c2++)
{
if(key[c1] == KEY[c2])
equal++;
}
}
return pos * 256 + equal;
}
int main()
{
for (int t = 0; t < 1; t++) //test case 50개
{
for (int i = 0; i < 200; i++)
{
KEY[i] = rand() % 255 + 1; //1~255
}
unsigned char key[200] = { 0, };
find_array(key); //you must implement this function
}
return 0;
}
//user_code.cpp
extern int check(unsigned char key[200]);
//you must implement this function
//below is my code take a long time(about 2sec for each case)
void find_array(unsigned char key[200])
{
unsigned char temp[200];
int result, pos, equal;
for (int k = 0; k < 200; k++)
temp[k] = 0;
for (int i = 0; i < 200; i++)
{
for (int val = 1; val <= 255; val++)
{
temp[i] = val;
result = check(temp);
equal = result % 256;
pos = (result - equal) / 256;
if (pos >= 1)
{
key[i] = val;
temp[i] = 0;
break;
}
}
}
}