Просеивание чисел

@svetlana123 · Регистрация: 18.01.2015

Author24 — интернет-сервис помощи студентам

Здравствуйте. Есть проблема со временем выыполнения алгоритма. Вот его суть. Пусть есть массив из чисел 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30. Нужно построить матрицу5х6 из данных чисел. Берем 1-е число массива - это 1, умножаем на 2, полученное число умножаем на 2 и т.д. Т.о. первая строка матрицы
1 2 4 8 16. Чтобы построить вторую строку, ищем в массиве 1-е число, которого нет в 1-ой строке матрицы - это 3, тогда вторая строка матрицы имеет вид 3 6 12 24 17, получаем именно 17, т.к. умножение идет по модулю 31. Таким образом, идем дальше и матрица имеет вид:
1 2 4 8 16
3 6 12 24 17
5 10 20 9 18
7 14 28 25 19
11 22 13 26 21
15 30 29 27 23
Моя реализация на c# выглядит так:
public int GetFirst(Int64[] Mas)//позиция ненулевого элемента
{
int k = 0;
for (int i = 0; i < 31; i++)
{
if (Mas[i] != 0)
{
k = i;
break;
}
}
return k;
}
for (int i = 0; i < 6; i++)
{
k = GetFirst(Mas);
Matr[i, 0] = Mas[k];
Mas[k] = 0;
for (int j = 1; j < 6; j++)
{
Matr[i, j] = 2 * Matr[i, j - 1] % 31;

for (int t = 0; t < 31; t++)
{
if (Mas[t] == Matr[i, j]) { k = t; break; }
}
Mas[k] = 0;

}
}
Может как-то можно по-другому? Т.к если исходный массив более 30000 очень долго работает!

@carlos13 · 02.03.2009, 00:51

Привет. Не знаю, какие у тебя результаты; такое работает ~ < 1 сек. Остальное время тратится на вывод данных.

Код

#include <iostream>
using namespace std;
//------------------------------
int const size_seq = 30000;
int const x_max = size_seq / 6;
int const y_max = size_seq / 5;
int ArrSeq [size_seq];
int SortArr [x_max][y_max];
//-------------------------------
int ReturnNumb (int);
//-------------------------------
int main ()
{
       int index_arr = 0; 

       for (int i = 0; i < size_seq; i++)
	{
		ArrSeq [i] = i + 1;	   
	}
    
	for (int i = 0; i < y_max; i++)
	{
		int val = ReturnNumb (index_arr);
		int tmp_val = val;
		
		for (int j = 0; j < x_max; j++)
		{
			SortArr [i][j] = tmp_val;
			//cout << SortArr [i][j] << "_";
			ArrSeq [tmp_val - 1] = 0;
                        tmp_val = 2 * tmp_val % (size_seq + 1); 
		}
		
		//cout << endl;
                index_arr = val - 1;
	}
//cout << endl;
return 0;
}
//---------------------------------
int ReturnNumb (int index_arr)
{
	for (int i = index_arr; i < size_seq; i++)
	{
		if (ArrSeq [i] != 0)
		{
			index_arr = i;
			return ArrSeq [i];
		}
	}
}

Новые блоги и статьи
Как написать микросервис на Go/Golang InfoMaster 14.01.2025 Определение микросервиса, преимущества использования Go/ Golang Микросервис – это архитектурный подход к разработке программного обеспечения, при котором приложение состоит из небольших, независимо. . .	Как написать микросервис с нуля на C# InfoMaster 14.01.2025 В современном мире разработки программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот архитектурный подход предполагает. . .	Как создать интернет-магазин на PHP и JavaScript InfoMaster 14.01.2025 В современном мире электронная коммерция стала неотъемлемой частью бизнеса. Создание собственного интернет-магазина открывает широкие возможности для предпринимателей, позволяя достичь большей. . .	Как написать Тетрис на Ассемблере InfoMaster 14.01.2025 Тетрис – одна из самых узнаваемых и популярных компьютерных игр, созданная в 1984 году советским программистом Алексеем Пажитновым. За прошедшие десятилетия она завоевала симпатии миллионы людей по. . .	Как создать игру "Танчики" на Unity3d и C# InfoMaster 14.01.2025 Разработка игр – это увлекательный процесс, сочетающий в себе творчество и технические навыки. В этой статье мы рассмотрим создание классической игры "Танчики" с использованием Unity3D и языка. . .	Организую платный онлайн микро-курс по доработке Android-клиента Telegram _Ivana 14.01.2025 Официальная версия и распространенные форки не полностью устраивают? Сделай свою кастомную версию клиента! 4 занятия по 2 часа (2 недели пн, ср 19:00-21:00 по Москве). Первое вводное занятие. . .
Как создать приложение для фитнеса для iOS/iPhone на Kotlin InfoMaster 14.01.2025 Создание собственного фитнес-приложения — это не только захватывающий, но и полезный процесс, ведь оно может стать вашим верным помощником на пути к здоровому и активному образу жизни. В современных. . .	Как создать приложение магазина для iOS/iPhone на Swift InfoMaster 14.01.2025 Введение в разработку iOS-приложений Разработка приложений для iPhone и других устройств на базе iOS открывает огромные возможности для создания инновационных мобильных решений. В данной статье мы. . .	Это работает. Скорость асинхронной логики велика. Вопрос видимо останется в стабильности. Плата - огонь! Hrethgir 13.01.2025 По прошлому проекту в Logisim Evolution https:/ / www. cyberforum. ru/ blogs/ 223907/ blog8781. html прилагаю файл архива проекта в Gowin Eda. Восьмибитный счётчик из сумматора+ генератор сигнала. . .	UserScript для подсветки кнопок языков программирования в зависимости от текущего раздела volvo 13.01.2025 В результате работы этого скрипта подсвечиваются нужные кнопки не только в форме быстрого ответа, но и при редактировании сообщения: / / ==UserScript== / / @name CF_DefaultLangSelect / / . . .	Введение в модели и алгоритмы машинного обучения InfoMaster 12.01.2025 Машинное обучение представляет собой одну из наиболее динамично развивающихся областей искусственного интеллекта, которая фокусируется на разработке алгоритмов и методов, позволяющих компьютерам. . .	Как на Python создать нейросеть для решения задач InfoMaster 12.01.2025 В контексте стремительного развития современных технологий особое внимание уделяется таким инструментам, как нейросети. Эти структуры, вдохновленные биологическими нейронными сетями, используются для. . .

@svetlana123 0 / 0 / 0 Регистрация: 18.01.2015 Сообщений: 4
		1
	Просеивание чисел 01.03.2009, 12:58. Показов 1335. Ответов 1 Метки нет (Все метки) Здравствуйте. Есть проблема со временем выыполнения алгоритма. Вот его суть. Пусть есть массив из чисел 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30. Нужно построить матрицу5х6 из данных чисел. Берем 1-е число массива - это 1, умножаем на 2, полученное число умножаем на 2 и т.д. Т.о. первая строка матрицы 1 2 4 8 16. Чтобы построить вторую строку, ищем в массиве 1-е число, которого нет в 1-ой строке матрицы - это 3, тогда вторая строка матрицы имеет вид 3 6 12 24 17, получаем именно 17, т.к. умножение идет по модулю 31. Таким образом, идем дальше и матрица имеет вид: 1 2 4 8 16 3 6 12 24 17 5 10 20 9 18 7 14 28 25 19 11 22 13 26 21 15 30 29 27 23 Моя реализация на c# выглядит так: public int GetFirst(Int64[] Mas)//позиция ненулевого элемента { int k = 0; for (int i = 0; i < 31; i++) { if (Mas[i] != 0) { k = i; break; } } return k; } for (int i = 0; i < 6; i++) { k = GetFirst(Mas); Matr[i, 0] = Mas[k]; Mas[k] = 0; for (int j = 1; j < 6; j++) { Matr[i, j] = 2 * Matr[i, j - 1] % 31; for (int t = 0; t < 31; t++) { if (Mas[t] == Matr[i, j]) { k = t; break; } } Mas[k] = 0; } } Может как-то можно по-другому? Т.к если исходный массив более 30000 очень долго работает! 0

	02.03.2009, 00:51