Как быстро найти массив, который включает в себя несколько чисел (1 ~ 255)? - PullRequest
0 голосов
/ 19 мая 2019

Я хочу решить проблему с алгоритмом. Не могли бы вы предложить какие-нибудь алгоритмы, работающие быстрее?

* Краткое описание проблемы - Найти тот же массив ключей [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;
            }
        }
    }
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...