Создание алгоритмов

@Lateralus · Регистрация: 05.11.2011

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

Не знаю, в тот ли раздел пишу, но у меня есть следующая проблема. Сегодня я потратил много часов на разработку одного алгоритма, не смог его разработать, и взял готовый(знаю, что так делать неправильно,и поэтому мне очень стыдно). Может, есть какие-то книги или упражнения или программы, которые помогут научиться строить алгоритмы.

@sereg · 09.12.2013, 17:26

могу посоветовать книгу:
Алгоритмы: построение и анализ
2-е издание
Томас Х. Кормен, Чарльз И. Лейзерсон

эта книга легко воспринимается как по мне, а также к алгоритму дополняется псевдокод.

@Lateralus · 09.12.2013, 17:28 **[ТС]**

Спасибо. Она у меня есть. Почитаю тогда, раз рекомендуешь.

@Igor3D · 09.12.2013, 17:35

А я давно не стыжусь если потратил много дней, но так и не смог. Это нормально, возможно "ларчик просто НЕ открывался" или мои знания недостаточны.

"Дайте какую-нибудь книжку" - это ничего не дает, энтузиазма чтения хватает ненадолго

Возможно Вам стоит рассказать проблему в которую уперлись - хотя бы здесь.

@gazlan · 09.12.2013, 17:45

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

Как очень удачное введение, порекомендовал бы Dasgupta, Papadimitriou, Vazirani "Algorithms" (легко ищется на англ., на русском видел только черновик перевода), превосходное изложение многих тем есть у Robert Sedgewick, посмотрите Ананий Левитин "Алгоритмы. Введение в разработку и анализ", все книги Дональда Кнута (с соавторами), Томас Кормен (с соавторами)"Алгоритмы: построение и анализ"... Это для начала :-), тема неисчерпаема.

@Lateralus · 09.12.2013, 17:50 **[ТС]**

Задача была следующая: из 2 одномерных массивов A[1..N] и B[1..M],отсортированных в порядке неубывания, сформировать одномерный массив С[1..N+M],состоящий из элементов обоих массивов, который сохраняет упорядоченность. Мой код, написан на Си, выполняю в Code::Blocks 12.11:

C
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
31
32
33
34
35
36
37
38
39
40
41
42
#define M 4
#define N 4
#include <stdio.h>
#include <stdlib.h>
int a[]= {1,2,3,4,4};
int b[]= {0,0,0,0,0};
int n,i,j,k;
int c[]={0,0,0,0,0,0,0,0,0,0};
int main()
{
    n=9;
    a[0]=9;
    a[1]=10;
    a[2]=12;
    a[3]=13;
    a[4]=14;
 
 
    b[0]=9;
    b[1]=10;
    b[2]=12;
    b[3]=13;
    b[4]=14;
 
    for (i=0;i<=N;i+=1)
    for (j=0;j<=M;j+=1)
    if(a[i]<=b[j])
    {
        c[i+j]=a[i];
        c[i+j+1]=b[j];
    }
    else if(a[i]>b[j])
    {
        c[i+j]=b[j];
        c[i+j+1]=a[i];
    }
    for (k=0;k<=N+M;k+=1)
        printf("c[%d] = %d ",k,c[k]);
 
 
    return 0;
}

Работает неправильно, что очевидно хорошему алгоритмисту.

@gazlan · 09.12.2013, 18:05

Сортировка слиянием

@Lateralus · 09.12.2013, 18:06 **[ТС]**

Спасибо,почитаю, так сказать.

@Igor3D · 09.12.2013, 18:51

Здесь надо ставить так чтобы избежать запутанной логики if'oв, напр

C++
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
struct CIter {
 CIter( const int * data, int count ) : mData(data), mCount(count), mPos(0) {}
 bool HasValue( void ) const { return mPos < mCount; }
 int Value( void ) const { return mData[mPos]; }
 void operator ++ ( void ) { ++mPos; } 
 
 bool operator < ( const CIter & sec ) const
 {
   if (!HasValue()) return false;
   if (!sec.HasValue()) return true;
   return Value() < sec.Value();
 } 
 
// data
private:
 const int * mData;
 int mCount, mPos;
};
 
//---------- main -----------
int index = 0;
CIter itA(a, N), itB(b, M);
while (itA.HasValue() || itB.HasValue()) {
 CIter & it = (itA < itB) ? itA : itB;
 c[index++] = it.Value();
 ++it;
}
assert(index == N + M);

@Lateralus · 09.12.2013, 19:41 **[ТС]**

Спасибо,Igor3D,почитаю код.

@Qwertiy · 10.12.2013, 13:37

Сообщение от Lateralus

Работает неправильно, что очевидно хорошему алгоритмисту.

Лично мне очевидно, что писать слияние с квадратичной ассимптотикой - бред...
И изучать его правильность нет ни малейшего желания.

Сообщение от Igor3D

Здесь надо ставить так чтобы избежать запутанной логики if'oв, напр

Запутывать можно и не if'ами...

Сообщение от Lateralus

из 2 одномерных массивов A[1..N] и B[1..M],отсортированных в порядке неубывания, сформировать одномерный массив С[1..N+M],состоящий из элементов обоих массивов, который сохраняет упорядоченность.

JavaScript
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
var a=[1,4,5,7,99], b=[-7,33,55,99,106];
var q, w, i;
var res = new Array(a.length+b.length);
 
q=w=i=0;
while(true) {
  if(a[q]<b[w]) {
    res[i++]=a[q++];
    if(q==a.length) {
      while(w<b.length)
        res[i++]=b[w++];
      break;
    }
  }
  else {
    res[i++]=b[w++];
    if(w==b.length) {
      while(q<a.length)
        res[i++]=a[q++];
      break;
    }
  }
}
 
console.log(res);

Добавлено через 2 минуты
Хм.. Я перемудрил... Можно же проще:

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var a=[1,4,5,7,99], b=[-7,33,55,99,106];
var q, w, i;
var res = new Array(a.length+b.length);
 
q=w=i=0;
 
while(q<a.length && w<b.length)
  res[i++] = a[q]<b[w] ? a[q++] : b[w++];
 
while(q<a.length)
  res[i++] = a[q++];
 
while(w<b.length)
  res[i++] = b[w++];
 
console.log(res);

@Igor3D · 10.12.2013, 13:52

Да, второй вариант лучше - в первом не учитывается что длина одного их исходных массивов может быть нулевой. Все равно отслеживание q, w напрягает, пусть и немного.

Возвращаясь к теме, мне кажется проблема не в "недостатке алгоритмов", они здесь ни при чем. Просто нет еще техники/опыта программирования, ничего страшного, накопится

@Qwertiy · 10.12.2013, 13:57

Сообщение от Igor3D

в первом не учитывается что длина одного их исходных массивов может быть нулевой

Да, точно. Спасибо.

Сообщение от Igor3D

Все равно отслеживание q, w напрягает, пусть и немного.

Хм.. Какое отслеживание?

Сообщение от Igor3D

Просто нет еще техники/опыта программирования, ничего страшного, накопится

Согласен.

@Igor3D · 10.12.2013, 14:22

Сообщение от Qwertiy

Хм.. Какое отслеживание?

Просто неплохие шансы вместо q написать w или наоборот - ведь обращений к ним много. Ну и с пресловутой общностью неважно, напр на входе не массивы а std::list - и все по новой. Хотя с др стороны конкретная реализация яснее

@Qwertiy · 10.12.2013, 15:25

Сообщение от Igor3D

Просто неплохие шансы вместо q написать w или наоборот - ведь обращений к ним много.

Согласен. Но вообще, такая проблема с индексами периодически возникает в любом коде. Даже как-то не могу представить нормальный код без циклов. А хуже всего то, что как правило опечатки в индексах сложно найти...

Сообщение от Igor3D

Ну и с пресловутой общностью неважно, напр на входе не массивы а std::list - и все по новой.

Ну, при том что код на js, я даже не знаю, что можно подсунуть, чтобы это не работало.
Если говорить о си, то можно сразу спокойно вместо счётчиков инкрементить указатели. Тогда переход на итераторы не потребует никаких изменений кроме их иницилизации.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Lateralus 8 / 8 / 0 Регистрация: 05.11.2011 Сообщений: 81

	Создание алгоритмов 09.12.2013, 17:15. Показов 1760. Ответов 14 Метки нет (Все метки) Не знаю, в тот ли раздел пишу, но у меня есть следующая проблема. Сегодня я потратил много часов на разработку одного алгоритма, не смог его разработать, и взял готовый(знаю, что так делать неправильно,и поэтому мне очень стыдно). Может, есть какие-то книги или упражнения или программы, которые помогут научиться строить алгоритмы. 0

@sereg 1 / 1 / 0 Регистрация: 30.04.2012 Сообщений: 48
	09.12.2013, 17:26
	могу посоветовать книгу: Алгоритмы: построение и анализ 2-е издание Томас Х. Кормен, Чарльз И. Лейзерсон эта книга легко воспринимается как по мне, а также к алгоритму дополняется псевдокод. 0

@Lateralus 8 / 8 / 0 Регистрация: 05.11.2011 Сообщений: 81
	09.12.2013, 17:28 [ТС]
	Спасибо. Она у меня есть. Почитаю тогда, раз рекомендуешь. 0

@Igor3D 1963 / 819 / 114 Регистрация: 01.10.2012 Сообщений: 4,769 Записей в блоге: 2
	09.12.2013, 17:35
	А я давно не стыжусь если потратил много дней, но так и не смог. Это нормально, возможно "ларчик просто НЕ открывался" или мои знания недостаточны. "Дайте какую-нибудь книжку" - это ничего не дает, энтузиазма чтения хватает ненадолго Возможно Вам стоит рассказать проблему в которую уперлись - хотя бы здесь. 0

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	09.12.2013, 17:45
	По построению "сферических коров в вакууме" не видел, а по конкретным разделам есть немало книг, где на примерах разбираются методы решения задач и оценивается их сложность и возможные улучшения. Как очень удачное введение, порекомендовал бы Dasgupta, Papadimitriou, Vazirani "Algorithms" (легко ищется на англ., на русском видел только черновик перевода), превосходное изложение многих тем есть у Robert Sedgewick, посмотрите Ананий Левитин "Алгоритмы. Введение в разработку и анализ", все книги Дональда Кнута (с соавторами), Томас Кормен (с соавторами)"Алгоритмы: построение и анализ"... Это для начала :-), тема неисчерпаема. 0

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	09.12.2013, 18:05
	Сортировка слиянием 0

@Lateralus 8 / 8 / 0 Регистрация: 05.11.2011 Сообщений: 81
	09.12.2013, 18:06 [ТС]
	Спасибо,почитаю, так сказать. 0

@Lateralus 8 / 8 / 0 Регистрация: 05.11.2011 Сообщений: 81
	09.12.2013, 19:41 [ТС]
	Спасибо,Igor3D,почитаю код. 0

@Igor3D 1963 / 819 / 114 Регистрация: 01.10.2012 Сообщений: 4,769 Записей в блоге: 2
	10.12.2013, 13:52
	Да, второй вариант лучше - в первом не учитывается что длина одного их исходных массивов может быть нулевой. Все равно отслеживание q, w напрягает, пусть и немного. Возвращаясь к теме, мне кажется проблема не в "недостатке алгоритмов", они здесь ни при чем. Просто нет еще техники/опыта программирования, ничего страшного, накопится 1