Что такое set perm recursive в программирование
Перейти к содержимому

Что такое set perm recursive в программирование

  • автор:

Table of contents

Теги

mo, mos algorithm, sqrt, sqrt decomposition, hilbert, recursion, recursive curves

Sqrt-tree (part 2): modifications in O(sqrtN), lazy propagation

Автор gepardo, история, 6 лет назад ,

Some time ago I created a blog post about Sqrt-tree. If you didn’t read this post, please do it now.

But earlier, we were able just to answer the queries on a static array. Now we will make our structure more «dynamic» and add update queries there.

Update queries

Consider a query that does the assignment ax = val . We need to perform this query fast enough.

Naive approach

First, let’s take a look of what is changed in our tree when a single element changes. Consider a tree node with length l and its arrays: , and . It is easy to see that only elements from and will change (only inside the block with the changed element). will change O(l) elements. Therefore, total update count per node is O(l) .

We remember that any element x is present in exactly one tree node at each layer. Root node (layer 0 ) has length O(n) , nodes on layer 1 have length , nodes on layer 2 have length , etc. So the time complexity per update is .

But it’s too slow. Can it be done faster?

Теги

data structure, sqrt-decomposition, tree, log log n, implement yourself, lazy, segment tree 2.0

Длинка в Pascal

Автор gepardo, история, 6 лет назад ,

Когда говорят про языки программирования со встроенной реализацией длинной арифметики, обычно говорят о таких языках, как Java или Python. Сегодня я расскажу про длинку в языке Pascal, а, точнее, в его реализации Free Pascal Compiler.

Простейший код, который читает два «длинных» числа и складывает их, выглядит так:

program sum; uses gmp; var sa, sb: string; a, b: MPInteger; begin readLn(sa); readLn(sb); a := sa; b := sb; writeLn(string(a + b)); end. 

Модуль gmp содержит все классы и операторы дя работы с «длинными» числами.

Как он работает? Этот модуль содержит заголовки функций, импортируемые из GNU Multiprecision Library. Программа и библиотека связываются динамически, поэтому для работы программы необходимо, чтобы эта библиотека была установлена. К счастью, в большинстве дистрибутивов Linux она установлена по умолчанию и поэтому может быть использована в таких системах, как ejudge и Яндекс.Контест. В тестирующих системах на Windows библиотека не установлена, поэтому такая штука не сработает.

Для удобства работы в модуле реализована объектно-ориентированная обёртка над функциями libgmp , для которой перегружены все необходиые операторы (да-да, во Free Pascal есть перегрузка операторов!)

Что еще примечательно, в libgmp реализовано быстрое извлечение целочисленного квадратного корня. Поэтому можно написать очень простой, быстрый и короткий код на задачу F с заочного тура Открытки.

program F;   uses gmp; var num: string; mpNum: MPInteger; root, rem: MPInteger; begin readLn(num); mpNum := num; mpNum := mpNum - 1; z_sqrtrem(root, rem, mpNum); if rem < root then begin writeln(string(rem + 1)); end else begin writeln(string(2 * root + 1 - rem)); end; end. 

Теги

длинка, паскаль, открытка, паскаль жив, gmp

Sqrt-tree: answering queries in O(1) with O(NloglogN) preprocessing.

Автор gepardo, история, 6 лет назад ,

Some time ago I invented an interesting data structure and I'd like to share it with the community. Maybe, it was known before, and if you knew about it before my blog post, please share the link to the source.

What can the data structure do?

Given an array a that contains n elements and the operation op that satisfies associative property: (x op y)op z = x op(y op z) is true for every x , y and z .

So, such operations as gcd , min , max , sum, multiplication, and , or , xor , etc. satisfy these conditions.

Also we have some queries l, r . For each query, we need to find al op al + 1 op . op ar . Let's call such queries q(l, r) .

My data structure can process such queries in O(1) time with preprocessing time and memory.

How it works?

Теги

data structure, sqrt-decomposition, tree, log log n

Доступ к архивам контестов

Автор gepardo, история, 6 лет назад ,

Доброго времени суток, Codeforces!

Было бы очень неплохо, если бы все материалы соревнований Codeforces были бы доступны публично и была бы возможность выкачивать архивы. На это есть несколько причин:

  • Проще проводить тренировки. На тренировках могут попадаться разные задачи, и бывает неплохо собрать их в один контест в одной тестирующей системе. Существование тестов в открытом виде сильно поможет проведению тренировок таким образом.
  • Большая доступность. Если сайт упадет или уйдет в оффлайн на некоторое время, архивы с задачами все равно останутся, и можно будет тестировать их локально.
  • Лучшая сохранность задач. Архивы с задачами будут храниться не на одном только Codeforces. Если утеряется часть задач на серверах, то восстановить их будет меньшей проблемой.

Возможно контраргументом против открытия тестов будет то, что синие и зеленые будут скачивать тесты вместо того, чтобы искать баг полностью самостоятельно. Но, 1) небольшие тесты и так доступны и 2) можно дать доступ к материалам только участникам с тренерским доступом.

Такая идея уже выдвигалась на заре существования сайта, вот блог от MikeMirzayanov на эту тему. Но, судя по всему, прогресс по этому вопросу остановился.

Лучше всего, конечно, если бы MikeMirzayanov выложил бы матералы централизованно. Жду его ответа на этот пост. Но я хотел бы выложить архивы своих контестов, не дожидаясь его решения:

Есть еще пост от Arpa, в котором он выложил материалы своего раунда Codeforces Round 383 (Div. 1).

Теги

контесты, архивы, предложение, codeforces

Codeforces Round #404. Разбор.

Автор gepardo, история, 7 лет назад ,

Перед вами разбор задач сегодняшнего контеста. Я постарался расписать решения задач как можно более подробно, но если что-то будет непонятно, смело пишите в комментариях! 🙂

Подсказка
Разбор
Tutorial is loading.

#include #include using namespace std; int main() < ios_base::sync_with_stdio(false); mapvals; vals["Tetrahedron"] = 4; vals["Cube"] = 6; vals["Octahedron"] = 8; vals["Dodecahedron"] = 12; vals["Icosahedron"] = 20; int n; cin >> n; int res = 0; for (int i = 0; i < n; i++) < string s; cin >> s; res += vals[s]; > cout

Код Java

import java.io.*; import java.util.*; public class PolyhedronSums < public static void main(String[] args) throws Exception < BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); HashMapvals = new HashMap(); vals.put("Tetrahedron", 4); vals.put("Cube", 6); vals.put("Octahedron", 8); vals.put("Dodecahedron", 12); vals.put("Icosahedron", 20); int n = Integer.parseInt(reader.readLine()); int res = 0; for (int i = 0; i < n; i++) < res += vals.get(reader.readLine()); >writer.write(Integer.toString(res)); reader.close(); writer.close(); > > 

Код Python

vals = < 'Tetrahedron': 4, 'Cube': 6, 'Octahedron': 8, 'Dodecahedron': 12, 'Icosahedron': 20 >n = int(input()) ans = 0 for i in range(0, n): ans += vals[input()] print(ans) 

Подсказка

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

Разбор
Tutorial is loading.

#include #include const int infinity = 1234567890; using namespace std; int main() < ios_base::sync_with_stdio(false); int n; cin >> n; vector > a(n); for (int i = 0; i < n; i++) < cin >> a[i].first >> a[i].second; > int m; cin >> m; vector > b(m); for (int i = 0; i < m; i++) < cin >> b[i].first >> b[i].second; > int minR1 = infinity, maxL1 = -infinity; int minR2 = infinity, maxL2 = -infinity; for (int i = 0; i < n; i++) < maxL1 = max(maxL1, a[i].first); minR1 = min(minR1, a[i].second); >for (int i = 0; i < m; i++) < maxL2 = max(maxL2, b[i].first); minR2 = min(minR2, b[i].second); >int res = max(maxL2 - minR1, maxL1 - minR2); cout

Код Java

import java.io.*; import java.util.*; public class TwoSegments < public static final int infinity = 1234567890; public static class Segment < public int l; public int r; public Segment(int aL, int aR) < l = aL; r = aR; >> private static Segment[] readList(BufferedReader reader) throws Exception < int n = Integer.parseInt(reader.readLine()); Segment[] res = new Segment[n]; for (int i = 0; i < n; i++) < StringTokenizer tokenizer = new StringTokenizer(reader.readLine()); int l = Integer.parseInt(tokenizer.nextToken()); int r = Integer.parseInt(tokenizer.nextToken()); res[i] = new Segment(l, r); >return res; > public static void main(String[] args) throws Exception < BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); Segment[] a = readList(reader); Segment[] b = readList(reader); int minR1 = infinity, maxL1 = -infinity; int minR2 = infinity, maxL2 = -infinity; for (int i = 0; i < a.length; i++) < maxL1 = Math.max(maxL1, a[i].l); minR1 = Math.min(minR1, a[i].r); >for (int i = 0; i < b.length; i++) < maxL2 = Math.max(maxL2, b[i].l); minR2 = Math.min(minR2, b[i].r); >int res = Math.max(maxL2 - minR1, maxL1 - minR2); writer.write(Integer.toString(Math.max(res, 0))); reader.close(); writer.close(); > > 

Код Python

infinity = 1234567890 minR1 = minR2 = infinity maxL1 = maxL2 = -infinity n = int(input()) for i in range(0, n): (l, r) = map(int, input().split()) maxL1 = max(maxL1, l) minR1 = min(minR1, r) m = int(input()) for i in range(0, m): (l, r) = map(int, input().split()) maxL2 = max(maxL2, l) minR2 = min(minR2, r) res = max(maxL2 - minR1, maxL1 - minR2); print(max(res, 0)) 

В этой задаче были слабые претесты. Это было сделано для того, чтобы спровоцировать побольше взломов. И да, я предупреждал в анонсе 🙂

Подсказка

Промоделируйте процесс, чтобы узнать, как изменялось количество зерна в амбаре.

Разбор
Tutorial is loading.

#include #include using namespace std; int main() < ios_base::sync_with_stdio(false); int64_t n, m; cin >> n >> m; if (n else < n -= m; int64_t l = 0, r = 2e9; while (l < r) < int64_t m = (l + r) / 2; int64_t val = m * (m+1) / 2; if (val >= n) < r = m; >else < l = m+1; >> cout return 0; > 

Код Java

import java.io.*; import java.util.*; public class SparrowsJava < public static void main(String[] args) throws Exception < BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer tokenizer = new StringTokenizer(reader.readLine()); long n = Long.parseLong(tokenizer.nextToken()); long m = Long.parseLong(tokenizer.nextToken()); if (n else < n -= m; long l = 0, r = (long)2e9; while (l < r) < long med = (l + r) / 2; long val = med * (med+1) / 2; if (val >= n) < r = med; >else < l = med+1; >> writer.write(Long.toString(l + m)); > reader.close(); writer.close(); > > 

Код Python

(n, m) = map(int, input().split()) if n = n: r = m else: l = m+1 print(l + aM) 

Подсказка

Решите упрощенную версию задачи. Пусть в нашей последлвательности сначала идет x открывающих скобок, потом y закрывающих скобок, притом последнюю открывающую скобку обязательно включать в ППСП. Используйте наивное решение, чтобы посмотреть, как будет выглядеть ответ. Подумайте, как действовать дальше.

Разбор
Tutorial is loading.

#include #include #include using namespace std; int mod = (int)1e9 + 7; int64_t extGcd(int64_t a, int64_t b, int64_t& x, int64_t& y) < if (!a) < x = 0; y = 1; return b; >int64_t x1, y1; int64_t d = extGcd(b % a, a, x1, y1); x = y1 - (b / a) * x1; y = x1; return d; > inline int addMod(int a, int b, int m = mod) < return ((int64_t)a + b) % m; >inline int mulMod(int a, int b, int m = mod) < return ((int64_t)a * b) % m; >inline int divMod(int a, int b, int m = mod) < int64_t x, y; int64_t g = extGcd(b, m, x, y); if (g != 1) < cerr x = (x % m + m) % m; return mulMod(a, x, m); > const int factRange = 1000000; int fact[factRange]; inline void precalcFactorials() < fact[0] = 1; for (int i = 1; i < factRange; i++) < fact[i] = mulMod(fact[i-1], i); >> inline int F(int n) < return (n < 0) ? 0 : fact[n]; >inline int C(int k, int n) < return divMod(F(n), mulMod(F(n-k), F(k))); >int main() < ios_base::sync_with_stdio(false); string s; cin >> s; int len = s.size(); precalcFactorials(); vector opnLeft(len), clsRight(len); opnLeft[0] = (s[0] == '(') ? 1 : 0; for (int i = 1; i < len; i++) < opnLeft[i] = opnLeft[i-1] + ((s[i] == '(') ? 1 : 0); >clsRight[len-1] = (s[len-1] == ')') ? 1 : 0; for (int i = len-2; i >= 0; i--) < clsRight[i] = clsRight[i+1] + ((s[i] == ')') ? 1 : 0); >int res = 0; for (int i = 0; i < len; i++) < if (s[i] != '(' || clsRight[i] == 0) < continue; >int add = C(opnLeft[i], opnLeft[i] + clsRight[i] - 1); res = addMod(res, add); > cout

Код Java

import java.io.*; import java.util.*; public class BracketsJava < public static int mod = (int)1e9 + 7; public static class ExtGcdResult < long x; long y; >public static long extGcd(long a, long b, ExtGcdResult res) < if (a == 0) < res.x = 0L; res.y = 1L; return b; >ExtGcdResult newRes = new ExtGcdResult(); long d = extGcd(b % a, a, newRes); res.x = newRes.y - (b / a) * newRes.x; res.y = newRes.x; return d; > public static final int addMod(int a, int b) < return (int)(((long)a + b) % mod); >public static final int mulMod(int a, int b) < return (int)(((long)a * b) % mod); >public static final int divMod(int a, int b) < ExtGcdResult res = new ExtGcdResult(); long g = extGcd(b, mod, res); if (g != 1) < System.out.println("Bad gcd!"); for (;;); >int q = (int)((res.x % mod + mod) % mod); return mulMod(a, q); > public static final int[] precalcFactorials() < int[] fact = new int[factRange]; fact[0] = 1; for (int i = 1; i < factRange; i++) < fact[i] = mulMod(fact[i-1], i); >return fact; > public static final int factRange = 1000000; public static final int[] fact = precalcFactorials(); public static final int F(int n) < return (n < 0) ? 0 : fact[n]; >public static final int C(int k, int n) < int res = divMod(F(n), mulMod(F(n-k), F(k))); return divMod(F(n), mulMod(F(n-k), F(k))); >public static void main(String[] args) throws Exception < BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); String s = reader.readLine(); int len = s.length(); int[] opnLeft = new int[len], clsRight = new int[len]; opnLeft[0] = (s.charAt(0) == '(') ? 1 : 0; for (int i = 1; i < len; i++) < opnLeft[i] = opnLeft[i-1] + ((s.charAt(i) == '(') ? 1 : 0); >clsRight[len-1] = (s.charAt(len-1) == ')') ? 1 : 0; for (int i = len-2; i >= 0; i--) < clsRight[i] = clsRight[i+1] + ((s.charAt(i) == ')') ? 1 : 0); >int res = 0; for (int i = 0; i < len; i++) < if (s.charAt(i) != '(' || clsRight[i] == 0) < continue; >int add = C(opnLeft[i], opnLeft[i] + clsRight[i] - 1); res = addMod(res, add); > writer.write(Integer.toString(res)); reader.close(); writer.close(); > > 

Приношу извининения, что эта задача не была оригинальной. Я постараюсь, чтобы такое больше не повторилось.

Если у вас в этой задаче TL или ML, не стоит думать, что ограничения по времени/памяти слишком узкие. Авторское решение работает за 1.2 секунды и тратит 9 МБ памяти.

Подсказка

Разделите все запросы на блоков. Затем разделите элементы на подвижные (те, которые будут изменяться в данном блоке) и неподвижные. Подумайте, как действовать дальше.

Разбор
Tutorial is loading.

// Thanks to netman for the idea for this wonderful solution :) #include #include #include #include #include using namespace std; class SQRTDecomposition < private: int n, sz; vectorval; vector blocks; public: inline void add(int v, int delta) < val[v] += delta; blocks[v / sz] += delta; >inline int sum(int l, int r) < if (l < 0) < l = 0; >if (r >= n) < r = n; >r++; int res = 0; int lBlock = (l + sz - 1) / sz, rBlock = r / sz; for (int i = lBlock; i < rBlock; i++) < res += blocks[i]; >int lBlockR = lBlock * sz, rBlockR = rBlock * sz; if (lBlockR >= rBlockR) < for (int i = l; i < r; i++) < res += val[i]; >> else < for (int i = l; i < lBlockR; i++) < res += val[i]; >for (int i = rBlockR; i < r; i++) < res += val[i]; >> return res; > inline void clear() < val.assign(val.size(), 0); blocks.assign(blocks.size(), 0); >SQRTDecomposition(int n, int sz) : n(n), sz(sz), val(n, 0), blocks((n + sz - 1) / sz, 0) < >>; struct ToProcess < int x, y1, y2, sgn, id; >; const int BLOCK_SZ_Q = 256; const int BLOCK_SZ_N = 512; const int MAX_N = 200000; int n, q; vector sortedL[MAX_N], sortedR[MAX_N]; SQRTDecomposition sum(MAX_N, BLOCK_SZ_N); int64_t ans[MAX_N], preAns[MAX_N]; pair queries[MAX_N]; vector goods; int p[MAX_N]; bool good[MAX_N]; inline void add(int q, int sgn, int id) < if (q-1 >= 0) < sortedL[q-1].push_back(); > if (q+1 < n) < sortedR[q+1].push_back(); > > int main() < ios_base::sync_with_stdio(false); cin >> n >> q; for (int i = 0; i < n; i++) < p[i] = i; >for (int i = 0; i < q; i++) < cin >> queries[i].first >> queries[i].second; queries[i].first--; queries[i].second--; > int64_t cnt = 0; for (int i = 0; i < q; i += BLOCK_SZ_Q) < int iEnd = min(q, i + BLOCK_SZ_Q); for (int j = 0; j < n; j++) < good[j] = false; >for (int j = i; j < iEnd; j++) < good[queries[j].first] = true; good[queries[j].second] = true; >goods.clear(); for (int j = 0; j < n; j++) < if (good[j]) < goods.push_back(j); >> int64_t goodCnt = 0; for (int j = 0; j < n; j++) < sortedL[j].clear(); sortedR[j].clear(); >for (int j = i; j < iEnd; j++) < int a = queries[j].first, b = queries[j].second; if (a == b) < ans[j] += goodCnt; continue; >for (int k = 0; k < (int)goods.size(); k++) < int q = goods[k]; if (q == a || q == b) < continue; >if ((p[q] < p[a] && q >a) || (p[q] > p[a] && q < a)) < goodCnt--; >if ((p[q] < p[b] && q >b) || (p[q] > p[b] && q < b)) < goodCnt--; >if ((p[q] < p[b] && q >a) || (p[q] > p[b] && q < a)) < goodCnt++; >if ((p[q] < p[a] && q >b) || (p[q] > p[a] && q < b)) < goodCnt++; >> if ((a < b && p[a] >p[b]) || (a > b && p[a] < p[b])) < goodCnt--; >else < goodCnt++; >ans[j] += goodCnt; add(a, -1, j); add(b, -1, j); swap(p[a], p[b]); add(a, +1, j); add(b, +1, j); > sum.clear(); for (int j = 0; j < n; j++) < if (!good[j]) < sum.add(p[j], 1); >for (int k = 0; k < (int)sortedL[j].size(); k++) < ToProcess &cur = sortedL[j][k]; int64_t res = sum.sum(cur.y1, cur.y2); res *= cur.sgn; preAns[cur.id] += res; >> sum.clear(); for (int j = n-1; j >= 0; j--) < if (!good[j]) < sum.add(p[j], 1); >for (int k = 0; k < (int)sortedR[j].size(); k++) < ToProcess &cur = sortedR[j][k]; int64_t res = sum.sum(cur.y1, cur.y2); res *= cur.sgn; preAns[cur.id] += res; >> for (int j = i; j < iEnd; j++) < if (j != i) < preAns[j] += preAns[j-1]; >ans[j] += cnt + preAns[j]; > cnt = ans[iEnd - 1]; > for (int i = 0; i < q; i++) < cout return 0; > 

Код Java

import java.io.*; import java.util.*; public class InversionNSqrtNNoVectors < private static final int BLOCK_SZ_Q = 256; private static final int BLOCK_SZ_N = 512; public static class ToProcess < public int x, y1, y2, sgn, id; public void set(int pX, int pY1, int pY2, int pSgn, int pId) < x = pX; y1 = pY1; y2 = pY2; sgn = pSgn; id = pId; >public ToProcess() < >> public static class ToProcessCompareAsc implements Comparator  < @Override public int compare(ToProcess o1, ToProcess o2) < return o1.x - o2.x; >> public static class ToProcessCompareDesc implements Comparator  < @Override public int compare(ToProcess o1, ToProcess o2) < return o2.x - o1.x; >> static int n, q; static int[] p; static ToProcess[] queryL, queryR; static int queryLCnt, queryRCnt; static SQRTDecomposition sum; static ToProcessCompareAsc ascCmp = new ToProcessCompareAsc(); static ToProcessCompareDesc descCmp = new ToProcessCompareDesc(); public static final void add(int q, int sgn, int id) < if (q-1 >= 0) < queryL[queryLCnt++].set(q-1, p[q]+1, n-1, sgn, id); >if (q+1 < n) < queryR[queryRCnt++].set(q+1, 0, p[q]-1, sgn, id); >> public static void main(String[] args) throws Exception < BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer tokenizer = new StringTokenizer(reader.readLine()); n = Integer.parseInt(tokenizer.nextToken()); q = Integer.parseInt(tokenizer.nextToken()); int[] qL = new int[q], qR = new int[q]; long[] ans = new long[q], preAns = new long[q]; p = new int[n]; for (int i = 0; i < n; i++) < p[i] = i; >for (int i = 0; i < q; i++) < tokenizer = new StringTokenizer(reader.readLine()); qL[i] = Integer.parseInt(tokenizer.nextToken()) - 1; qR[i] = Integer.parseInt(tokenizer.nextToken()) - 1; >long cnt = 0; boolean[] good = new boolean[n]; int[] goods = new int[n]; int goodsSize = 0; queryL = new ToProcess[4 * BLOCK_SZ_Q]; queryR = new ToProcess[4 * BLOCK_SZ_Q]; for (int j = 0; j < 4 * BLOCK_SZ_Q; j++) < queryL[j] = new ToProcess(); queryR[j] = new ToProcess(); >SQRTDecomposition sum = new SQRTDecomposition(n, BLOCK_SZ_N); for (int i = 0; i < q; i += BLOCK_SZ_Q) < int iEnd = Math.min(q, i + BLOCK_SZ_Q); Arrays.fill(good, false); for (int j = i; j < iEnd; j++) < good[qL[j]] = true; good[qR[j]] = true; >goodsSize = 0; for (int j = 0; j < n; j++) < if (good[j]) < goods[goodsSize++] = j; >> long goodCnt = 0; queryLCnt = 0; queryRCnt = 0; for (int j = i; j < iEnd; j++) < int a = qL[j], b = qR[j]; if (a == b) < ans[j] += goodCnt; continue; >for (int k = 0; k < goodsSize; k++) < int q = goods[k]; if (q == a || q == b) < continue; >if ((p[q] < p[a] && q >a) || (p[q] > p[a] && q < a)) < goodCnt--; >if ((p[q] < p[b] && q >b) || (p[q] > p[b] && q < b)) < goodCnt--; >if ((p[q] < p[b] && q >a) || (p[q] > p[b] && q < a)) < goodCnt++; >if ((p[q] < p[a] && q >b) || (p[q] > p[a] && q < b)) < goodCnt++; >> if ((a < b && p[a] >p[b]) || (a > b && p[a] < p[b])) < goodCnt--; >else < goodCnt++; >ans[j] += goodCnt; add(a, -1, j); add(b, -1, j); int tmp = p[a]; p[a] = p[b]; p[b] = tmp; add(a, +1, j); add(b, +1, j); > sum.clear(); Arrays.sort(queryL, 0, queryLCnt, ascCmp); int curL = 0; for (int j = 0; j < n; j++) < if (!good[j]) < sum.add(p[j], 1); >for (; curL < queryLCnt; curL++) < ToProcess cur = queryL[curL]; if (cur.x != j) < break; >int res = sum.sum(cur.y1, cur.y2); res *= cur.sgn; preAns[cur.id] += res; > > sum.clear(); Arrays.sort(queryR, 0, queryRCnt, descCmp); int curR = 0; for (int j = n-1; j >= 0; j--) < if (!good[j]) < sum.add(p[j], 1); >for (; curR < queryRCnt; curR++) < ToProcess cur = queryR[curR]; if (cur.x != j) < break; >int res = sum.sum(cur.y1, cur.y2); res *= cur.sgn; preAns[cur.id] += res; > > for (int j = i; j < iEnd; j++) < if (j != i) < preAns[j] += preAns[j-1]; >ans[j] += cnt + preAns[j]; > cnt = ans[iEnd - 1]; > for (int i = 0; i < q; i++) < writer.write(Long.toString(ans[i])); writer.newLine(); >reader.close(); writer.close(); > > class SQRTDecomposition < private int n; private int sz; private int[] val; private int[] blocks; public final void add(int v, int delta) < val[v] += delta; blocks[v / sz] += delta; >public final int sum(int l, int r) < if (l < 0) < l = 0; >if (r >= n) < r = n; >r++; int res = 0; int lBlock = (l + sz - 1) / sz, rBlock = r / sz; for (int i = lBlock; i < rBlock; i++) < res += blocks[i]; >int lBlockR = lBlock * sz, rBlockR = rBlock * sz; if (lBlockR >= rBlockR) < for (int i = l; i < r; i++) < res += val[i]; >> else < for (int i = l; i < lBlockR; i++) < res += val[i]; >for (int i = rBlockR; i < r; i++) < res += val[i]; >> return res; > public void clear() < Arrays.fill(val, 0); Arrays.fill(blocks, 0); >SQRTDecomposition(int pN, int pSz) < n = pN; sz = pSz; val = new int[n]; blocks = new int[(n + sz - 1) / sz]; >> 

Альтернативное решение от Vladik:

#include #include #include #include #include #include #include #include #define sqr(a) (a)*(a) #define all(a) (a).begin(), (a).end() using namespace std; template T next_int() < T ans = 0, t = 1; char ch; do < ch = getchar(); >while(ch while(ch >= '0' && ch return ans * t; > string next_token() < char ch; string ans = ""; do < ch = getchar(); >while(ch = ' ') < ans += ch; ch = getchar(); >return ans; > const long long INF = (long long)1e18 + 227 + 1; const int INFINT = (int)1e9 + 227 + 1; const int MAXN = (int)2e5 + 227 + 1; const int MOD = (int)1e9 + 7; const long double EPS = 1e-9; long long bin_pow(long long n, long long k) < if(!k) return 1; long long ans = bin_pow(n, k / 2); ans = ans * ans % MOD; if(k % 2) ans = ans * n % MOD; return ans; >struct tree < int size_block; int len; tree(int len) : len(len) < size_block = sqrt(len); kek.resize(len / size_block + 1, vector(size_block, 0)); pr_block.resize(len / size_block + 1, 0); > vector pr_block; vector  kek; void inc(int pos, int num) < int x = pos / size_block; for(int i = pos % size_block; i < size_block; i++) < kek[x][i] += num; >for(int i = 0; i else < pr_block[i] = pr_block[i - 1] + kek[i][size_block - 1]; >> int f(int a) < return a / size_block; >long long get(vector &a, int l, int r, bool ok = 1) < if(ok == 1) < l %= size_block; r %= size_block; >return a[r] - (l ? a[l - 1] : 0); > int get(int l, int r) < if(l >r) return 0; r = min(r, len); if(f(l) == f(r)) return get(kek[f(l)], l, r); int ans = 0; if(l % size_block) < ans += get(kek[f(l)], l, size_block - 1); l += size_block - l % size_block; >if(r % size_block != size_block - 1) < ans += get(kek[f(r)], 0, r); r -= r % size_block + 1; >ans += get(pr_block, f(l), f(r), 0); return ans; > int get_pref(int p) < return get(1, p - 1); >int get_suff(int p) < return get(p + 1, len); >> ; struct mda < vectora; vector t; int len, sz; long long ans; mda(int len) : len(len) < sz = 2000; ans = 0; a.resize(len + 1); for(int i = 1; i > int get_pref(int L, int R, int k) < int ans = 0; for(int l = 1; l R) continue; if(L return ans; > int get_suff(int L, int R, int k) < int ans = 0; for(int l = 1; l R) continue; if(L k); > return ans; > void del(int p, int k) < p = (p - 1) / sz; t[p].inc(k, -1); >void add(int p, int k) < p = (p - 1) / sz; t[p].inc(k, 1); >void sw(int i, int j) < if(i == j) return; if(i >j) swap(i, j); ans -= get_pref(i, j, a[i]); ans -= get_suff(i, j, a[j]); if(a[i] > a[j]) ans++; del(i, a[i]); del(j, a[j]); swap(a[i], a[j]); add(i, a[i]); add(j, a[j]); ans += get_pref(i, j, a[i]); ans += get_suff(i, j, a[j]); if(a[i] > a[j]) ans--; > > ; int main() < // freopen(".in", "r", stdin); int n, m; cin >> n >> m; mda t(n); for(int i = 0; i < m; i++) < int x, y; cin >> x >> y; t.sw(x, y); cout > 

Альтернативное решение от netman:

Код Java

import java.io.*; import java.util.*; public class NsqrtNlogNnetman implements Runnable < static class InputReader < BufferedReader reader; StringTokenizer tokenizer; InputReader(InputStream in) < reader = new BufferedReader(new InputStreamReader(in), 32768); tokenizer = null; >String next() < while (tokenizer == null || !tokenizer.hasMoreTokens()) < try < tokenizer = new StringTokenizer(reader.readLine()); >catch (IOException e) < e.printStackTrace(); throw new RuntimeException(e); >> return tokenizer.nextToken(); > int nextInt() < return Integer.parseInt(next()); >long nextLong() < return Long.parseLong(next()); >double nextDouble() < return Double.parseDouble(next()); >> static class Fenwick < int[] ft; Fenwick(int n) < ft = new int[n]; >void add(int r, int val) < while (r < ft.length) < ft[r] += val; r |= r + 1; >> int sum(int r) < int res = 0; while (r >= 0) < res += ft[r]; r = (r & (r + 1)) - 1; >return res; > void clear() < Arrays.fill(ft, 0); >> static class Query < int x, bound, sign, id; Query(int x, int bound, int sign, int id) < this.x = x; this.bound = bound; this.sign = sign; this.id = id; >> static void getOnPrefSmaller(List qrs, int r, int y, int id, int sign) < qrs.add(new Query(r, y, sign, id)); >static void getOnPrefBetween(List qrs, int r, int x, int y, int id, int sign) < getOnPrefSmaller(qrs, r, y, id, sign); getOnPrefSmaller(qrs, r, x, id, -sign); >static void getOnSegmentBetween(List qrs, int l, int r, int x, int y, int id, int sign) < if (x >y) return; getOnPrefBetween(qrs, r, x, y, id, sign); getOnPrefBetween(qrs, l, x, y, id, -sign); > @Override public void run() < InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); int n = in.nextInt(); int q = in.nextInt(); int[] l = new int[q]; int[] r = new int[q]; for (int i = 0; i < q; i++) < l[i] = in.nextInt() - 1; r[i] = in.nextInt() - 1; >int[] perm = new int[n]; for (int i = 0; i < n; i++) < perm[i] = n - i - 1; >final int BLOCK = 300; long inv = 0L; boolean[] isInteresting = new boolean[n]; long[] add = new long[q]; Fenwick f = new Fenwick(n); for (int i = 0; i < q; i += BLOCK) < int from = i, to = Math.min(i + BLOCK, q) - 1; Listlst = new ArrayList<>(); for (int j = from; j lst.sort(Integer::compareTo); lst = new ArrayList<>(new HashSet<>(lst)); int[] interestingPositions = lst.stream().mapToInt(x -> x).toArray(); for (int pos : interestingPositions) < isInteresting[pos] = true; >List qrs = new ArrayList<>(); for (int j = from; j r[j]) < int tmp = l[j]; l[j] = r[j]; r[j] = tmp; >if (perm[l[j]] < perm[r[j]]) < getOnSegmentBetween(qrs, l[j], r[j], perm[l[j]], perm[r[j]], j,-1); int leftValue = perm[l[j]]; int rightValue = perm[r[j]]; for (int pos : interestingPositions) < if (pos >l[j] && pos < r[j] && perm[pos] >leftValue && perm[pos] < rightValue) < add[j] -= 2; >> add[j]--; > else < getOnSegmentBetween(qrs, l[j], r[j], perm[r[j]], perm[l[j]], j,1); int leftValue = perm[l[j]]; int rightValue = perm[r[j]]; for (int pos : interestingPositions) < if (pos >l[j] && pos < r[j] && perm[pos] >rightValue && perm[pos] < leftValue) < add[j] += 2; >> add[j]++; > int tmp = perm[l[j]]; perm[l[j]] = perm[r[j]]; perm[r[j]] = tmp; > qrs.sort(Comparator.comparingInt(a -> -a.x)); f.clear(); for (int pos = 0; pos < n; pos++) < if (!isInteresting[pos]) < f.add(perm[pos], 1); >while (!qrs.isEmpty() && qrs.get(qrs.size() - 1).x == pos) < Query t = qrs.get(qrs.size() - 1); qrs.remove(qrs.size() - 1); add[t.id] += 2 * t.sign * f.sum(t.bound); >> for (int j = from; j for (int pos : interestingPositions) < isInteresting[pos] = false; >> out.close(); > public static void main(String[] args) < new Thread(null, new NsqrtNlogNnetman(), "1", 1L > 

Разбор задач Codeforces Round 404 (Div. 2)

Теги

разбор, антон, 404, контест, подсказки, тег не найден

Методика быстрого обучения программированию на основе изучения классов задач (11-15) Текст научной статьи по специальности «Математика»

АЛГОРИТМ / ALGORITHM / ПРОГРАММА / PROGRAM / ЯЗЫК ПРОГРАММИРОВАНИЯ ПАСКАЛЬ / PROGRAMMING LANGUAGE PASCAL / МАССИВ / ARRAY / ПРОЦЕДУРЫ И ФУНКЦИИ / PROCEDURES AND FUNCTIONS / РЕКУРСИЯ / RECURSION / МНОЖЕСТВО / SET / ЗАПИСЬ / RECORD

Аннотация научной статьи по математике, автор научной работы — Аляев Юрий Александрович

Предлагается методика быстрого обучения программированию на основе изучения классов задач, разработанная и применяющаяся на практике в процессе обучения программированию студентов вузов

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Аляев Юрий Александрович

Методика быстрого обучения программированию на основе изучения классов задач (16-17)
Методика быстрого обучения программированию на основе изучения классов задач (6-7)
Методика быстрого обучения программированию на основе изучения классов задач (18-19)
Методика быстрого обучения программированию на основе изучения классов задач (8-10)
Методика быстрого обучения программированию на основе изучения классов задач
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

Methods of the quick education to programming on base of the study of the classes of the problems (11-15)

Is offered methods of the quick education to programming on base of the study of the classes of the problems, designed and using in practice in process of the education to programming student high school

Текст научной работы на тему «Методика быстрого обучения программированию на основе изучения классов задач (11-15)»

1. Дорошенко Е.Г., Пак Н.И., Рукосуева Н.В., Хегай Л.Б. О технологии разработки ментальных учебников // Вестник Томского государственного педагогического университета (Tomsk State Pedagogical University Bulletin). 2013. Вып. 12 (140). С. 145-151.

2. Новак Д., Канас А. Теория построения и практика применения карт понятий. URL: http://cmap.ihmc.us/Publications/ResearchPapers/TheoryCmaps/TheoryUnderl

3. Шенк Ф.Б. Ментальные карты: конструирование географического пространства в Европе / пер. с нем. А. Жоровой // Политическая наука. Политический дискурс: История и современные исследования. 2001. Вып. 4. С. 4-17.

4. Шаталов В.Ф. Эксперимент продолжается. М.: Педагогика, 1989. 334 с.

5. Калитина В.В. Электронная энциклопедия как средство повышения уровня запоминания учебного материала // Вестник КГПУ. 2013. № 1 (23). С. 111-114.

6. Мюллер Х. Составление ментальных карт: метод генерации и структурирования идей / пер. с нем. В.В. Мартыновой, М.М. Демина. М.: Омега-Л, 2007. 126 с.

7. Пак Н.И. Гипермозг как основа становления ментальной дидактики. Интернет - свободный, безопасный, образовательный // Межрегион. науч.-практ. конф. (18-19 октября, 2013 г., г. Омск): сб. матер. / под общ. ред. М.П. Лапчика. Омск: Полиграфический центр КАН, 2013. 278 с.

8. Пак Н.И. Информационное моделирование: учебное пособие. // КГПУ им. В.П. Астафьева. Красноярск, 2010. 152 с.

9. Колесник В. Ментальные карты. URL: http://kolesnik.ru/2005/mindmapping

10. Петрова И.А., Ракова Е.П. Использование структурированных графических схем в изучении информатики // Успехи современного естествознания. 2013. № 10. С. 35-36.

11. Найссер У. Познание и реальность. М.: Прогресс, 1981. 252 с.

12. Бруннер Е.Ю. Применение технологии mind map в учебном процессе // Развитие международного сотрудничества в области образования в контексте Болонского процесса: материалы международной науч.-практ. конф. г. Ялта (5-6 марта 2008 г.). Ялта: РИО КГУ, 2008. Вып. 19. Ч. 1. С. 50-53.

13. Бабич А.В. Эффективная обработка информации (Mind mapping). URL: http://www.intuit.ru/studies/courses/647/503/lecture/11414?page=8

Use in educational process mental map

Damir Rashitovich Khakimov, Master SibGTU, Siberian State Technological University,

In this paper, the technique used in the training process of mental maps, the technology development which is based on the information model of thinking. Using this technique significantly affects the intensification of training and intensifying training activities due to higher than traditional teaching methods, the degree of visualization of the material presented.

Keywords: mental map, image, information model of thinking, structuring the learning process

МЕТОДИКА БЫСТРОГО ОБУЧЕНИЯ ПРОГРАММИРОВАНИЮ НА ОСНОВЕ ИЗУЧЕНИЯ КЛАССОВ ЗАДАЧ (11-15)

Юрий Александрович Аляев, доц., доц. кафедры программного обеспечения вычислительной техники и автоматизированных систем,

e-mail: alyr1@yandex.ru, Пермский военный институт внутренних войск МВД России,

Предлагается методика быстрого обучения программированию на основе изучения классов задач, разработанная и применяющаяся на практике в процессе обучения программированию студентов вузов.

Ключевые слова: алгоритм, программа, язык программирования Паскаль, массив, процедуры и функции, рекурсия, множество, запись

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

Этого удается добиться за счет применения рациональных методов обучения, прежде всего, последовательно проводя идеи обучения на основе выделения элементарных операций деятельности по построению алгоритмов и программ; выявления структуры алгоритма и форм ее записи на алгоритмическом языке; одинаковой формы алгоритма для решения задач с одинаковой структурой исходных данных [1-2]. Благодаря этим идеям, задачи по программированию удается разбить на ряд классов и типизировать методы решения задач каждого класса.

Предлагаемая методика быстрого обучения программированию на основе изучения классов задач, появилась и применяется на протяжении многих лет в процессе обучения программированию студентов пермских вузов благодаря В.П. Гладкову [2]. В статье рассматриваются методики решения по пяти (11-15) из девятнадцати выделенных классов задач (1-10 классы задач рассмотрены в [3-6]).

11. Данные типа string

Задача 1. Подсчитать, сколько раз в заданной строке встречается указанная буква. Решение 1. Пусть исходная строка хранится в переменной s, а искомая буква в переменной а. Для решения задачи будем просматривать строку s посимвольно и каждый символ сравнивать с заданной буквой. k:=0; for i:=1 to length(s) do

if copy(s,i,1)=a then k:=k+1;. Решение 2. Будем искать положение указанной буквы в строке до тех пор, пока ее удастся найти. Затем отбрасываем ту часть строки, где была найдена указанная буква, и повторяем поиск.

s:=copy(s,j+1 ,length(s)-j); j:=pos(a,s); end.

Задача 2. Проверить, входят ли в строку s две буквы а.

Решение. Для двух букв а, стоящих подряд: if pos('aa',s)>0 then write('входят') else write('HE входят'). Здесь требуется проверить наличие двух букв а, стоящих в любом месте строки. Эта задача является поисковой. Если строка закончится и две буквы а не будут найдены, то ответ на вопрос задачи отрицательный. Если при поиске будут найдены две буквы а, то ответ на вопрос задачи положительный. Для подсчета найденных букв а использовать счетчик. k:=0; f:=false; i:=1; while (i<=length(s)) and not f do if copy(s,i,1)='a' then begin k:=k+1;

if k=2 then f:=true;

then write('в строке есть две буквы а') else write^ строке нет двух букв а');. Другое решение этой задачи можно получить, основываясь на втором решении задачи 10.1.1.

then begin s:=copy(s,j+1,length(s)-j); j:=pos('a',s); if j>0

then write('в строке есть две буквы а') else write^ строке нет двух букв а');

else write^ строке нет двух букв а');.

Задача 3. В строке s заменить символы а на символы я.

Решение 1. Просматриваем строку посимвольно, удаляем найденный символ а, вставляем на его место я. for i:=1 to length(s) do if copy(s,i,1)='a' then begin delete(s,i,1) insert(V,s,i);

Решение 2. Просматриваем исходную строку посимвольно и переписываем в выходную строку символы, отличные от а. Вместо символа а переписываем символ я. s1:=''; < выходная строка >for i:=1 to length(s) do if copy(s,i,1)='a' then s1:=s1+V else s1:=s1+copy(s,i,1);. Решение 3. Оно основывается на решении 2 задачи 10.1.1. j:=pos('a',s); while j<>0 do

Задача 4. Будем считать словом любую последовательность букв и цифр. Строка состоит из слов, разделенных одним или несколькими пробелами. Удалить лишние пробелы, оставив между словами по одному пробелу.

Решение. Лишними пробелами называются второй, третий и т.д., следующие за первым пробелом. Следовательно, чтобы найти лишний пробел, нужно искать два пробела, стоящие рядом, и удалять второй пробел в каждой найденной паре. j:=pos(' ',s); while j<>0 do begin delete(s,j,1);

Задача 5. Строка символов - это любая последовательность символов, заключенная в апострофы. Задана строка символов, состоящая из слов и строк,

разделенных одним или несколькими пробелами. Удалить из строки все незначащие пробелы. Незначащими пробелами называются пробелы, не стоящие в апострофах.

Решение. Запишем формально определение незначащего пробела. Текущий пробел незначащий, если предыдущий символ является пробелом и этот пробел не стоит в апострофах. Введем логическую переменную p, которая принимает значение false, если предыдущий символ не является пробелом, и значение true, если предыдущий символ - пробел. Введем логическую переменную q, которая принимает значение false, если пробел находится не в апострофах, и значение true, если пробел в апострофах. Тогда формальное определение незначащего пробела запишется так: (copy(s,i,1)=' ') and p and not q.

Составляем программу: p:=false; q:=false; s1:='';

for i:=1 to length(s) do begin if not((copy(s,i,1)=' ') and p and not q) then s1:=s1+copy(s,i,1); if copy(s,i,1)=' ' then p:=true else p:=false; if copy(s,i,1)='''' then q:=not q; end;.

Задача 6. Подсчитать количество гласных букв русского алфавита в строке. Решение. Гласная буква - это такая буква, которая принадлежит множеству гласных букв. Для решения задачи просматриваем строку посимвольно и проверяем каждый символ на принадлежность гласным буквам: k:=0; for i:=1 to length(s) do if pos(copy(s,i,1),'аоуэыяёюеи')>0 then k:=k+1;.

Задача 7. Задано предложение, состоящее из слов, разделенных одним или несколькими пробелами. Определить самое длинное слово предложения.

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

то запоминаем его>

else if copy(s,i,1)<>' ' then ss:=ss+copy(s,i,1);

Задача 8. Задано предложение, состоящее из слов, разделенных одним или несколькими пробелами. Расположить слова предложения в алфавитном порядке.

Решение. Перепишем слова предложения по одному в элементы одномерного массива. Отсортируем массив по возрастанию и перепишем слова из массива в строку. const nn=100; type mas=array[1..nn]of string; var a:mas; i,j , k:integer; s,

write('Введите строку '); readln(s);

if a[i]>a[j] then begin

for i:=1 to k do s:=s+a[i]+' '; write(s); end.

12. Процедуры и функции

Задача 1. Написать программы для вычисления числа сочетаний из n по m, оформив вычисления факториала процедурой без параметров, процедурой с параметрами, функцией. Сравнить решения.

Решение 1. Воспользуемся известной формулой: n!

procedure fact1; var i:longint; begin p:=1;

for i:=1 to q do p:=p*i;

begin write('Введите n и m '); readln(n,m);

write('Число сочетаний из ',n,' по ',m,' равно ',c); end.

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

procedure fact2(q:longint;var p:longint); var i:longint; begin p:=1;

for i:=1 to q do p:=p*i;

begin write('Введите n и m '); readln(n,m); fact2(n,fn); fact2(m,fm); fact2(n-m,fnm); c:=fn div (fm*fnm);

write('Число сочетаний из ',n,' по ',m,' равно ',c); end.

c:longint; function fact3 (q: longint): longint; var i:longint; begin p:=1;

for i:=1 to q do p:=p*i; fact3:=p;

begin write('Введите n и m '); readln(n,m);

write('Число сочетаний из ',n,' по ',m,' равно ', fact3(n) div (fact3(m)*fact3(n-m))); end.

Задача 2. Даны два числа a и b. Разработать алгоритм и написать программу для определения наибольшего общего делителя (НОД) трех величин: a+b, I a-b I , a-b. Расчет НОД двух чисел оформить в виде пользовательской процедуры.

Математическая модель данной задачи имеет вид:

Расчет: x=a+b; y=| a-b I ; z=a-b.

Для расчета наибольшего общего делителя используем следующее выражение: нод^у^^нодснод^у)^). Для расчета НОД двух чисел используем алгоритм Евклида.

Фрагмент алгоритма для расчета наибольшего общего делителя k двух чисел n и m имеет вид:

Цикл-ПОКА (m*n); Если m>n То;

n:=n-m; Конец-Если; Конец-Цикла; k:=m;

В Паскаль-программе пользовательская процедура размещается в разделе описания процедур и функций.

procedure evklid(m,n:integer; var k:integer);

while m<>n do if m>n then m:=m-n else n:=n-m; k:=m; end;

writeln('a=',a,' b=',b); evklid(a+b,abs(a-b),c); evklid(c,a*b,c); writeln('нод=',c);

В данной программе обращение к пользовательской процедуре осуществляется дважды: первый раз - для расчета НОД суммы и модуля разности чисел a и b, второй раз - для расчета НОД числа, полученного от первого обращения к процедуре и произведения чисел a и b.

Пользовательская процедура имеет три формальных параметра: параметры-значения - m и n, а также параметр-переменную - k. Формальному параметру k соответствует фактический параметр с, с помощью которого выводится на печать искомый результат.

Задача 3. Решить задачу 11.2.2, используя для нахождения НОД пользовательскую функцию. Программа на языке Паскаль для решения этой задачи имеет следующий вид:

function evklid(m,n:integer) : integer; begin

while m<>n do if m>n then m:=m-n

evklid:=m; end; begin read(a,b);

writeln('a=',a,' b=',b); c:=evklid(evklid(a+b,abs(a-b)),a*b); writeln('нод=',c);

Для вызова пользовательской функции применяется оператор присваивания, в котором в качестве операнда используется обращение к функции, содержащее имя функции и список фактических параметров. В соответствии с правилами приоритета первым выполняется обращение evklid(a+b,abs(a-b)). Для возвращения результата решения пользовательская функция должна содержать оператор присваивания, у которого в левой части должно стоять имя функции, а в правой - возвращаемый в основную программу результат.

Задача 1. Известно рекурсивное определение факториала:

fi, если n = 0 или n = 1, n =\

Здесь n - неотрицательно. Записать эту функцию на языке Паскаль. Решение. В первой строке определения явно указано, как вычислить факториал, если аргумент равен нулю или единице. В любом другом случае для вычисления n! необходимо вычислить предыдущее значение (п-1)! и умножить его на n. Уменьшающееся значение гарантирует, что, в конце концов, возникнет необходимость найти 1! или 0!, которые вычисляются непосредственно. program task5;

function fact(i: integer) :integer; begin if (i=1) or (i=0) then fact:=1 else fact:=fact(i-1)*i;

begin write('Введите нужное значение n '); readln(n);

writeln('Факториал ',n,' равен ',fact(n)); end.

Вспомним, что на время выполнения вспомогательного алгоритма основной алгоритм приостанавливается. При вызове новой копии рекурсивного алгоритма вновь выделяется место для всех переменных, объявляемых в нем, причем переменные других копий будут недоступны. При удалении копии рекурсивного алгоритма из памяти удаляются и все его переменные. Активизируется предыдущая копия рекурсивного алгоритма, становятся доступными ее переменные. Пусть необходимо вычислить 4!. Основной алгоритм: вводится n=4, вызов fact(4). Основной алгоритм

приостанавливается, вызывается и работает fact(4): 4<>1 и 4<>0, поэтому fact:=fact(3)*4. Работа функции приостанавливается, вызывается и работает fact(3): 3<>1 и 3<>0, поэтому fact:=fact(2)*3. В данный момент в памяти компьютера две копии функции fact. Вызывается и работает fact(2): 2<>1 и 2<>0, поэтому fact:=fact(1)*2. В памяти компьютера уже три копии функции fact и вызывается четвертая. Вызывается и работает fact(1): 1=1, поэтому fact(1)=1. Работа этой функции завершена, продолжает работу fact(2). fact(2):=fact(1)*2=1*2=2. Работа этой функции также завершена, и продолжает работу функция fact(3). fact(3):=fact(2)*3=2*3=6. Завершается работа и этой функции, и продолжает работу функция fact(4). fact(4):=fact(3)*4=6*4=24. Сейчас управление передается в основную программу и печатается ответ: «Факториал 4 равен 24».

14. Тип данных множество

Задача 1. Задать множество целых чисел от заданного числа до числа в три раза большего, чем заданное.

Решение. Используем описание множеств на языке Паскаль и операторы для работы с множествами.

Если количество элементов n в множестве известно заранее, то задача решается

type setnum=set of byte; const mn:setnum=[n..3*n];

. Если начальное значение задается пользователем, то задача решается так: type setnum=set of byte; var mn:setnum; n,i:byte;

begin write('задайте первый элемент множества ');

else write('заданное количество элементов не поместится в множестве '); end.

Задача 2. Вывести элементы множества, содержащего прописные и строчные буквы латинского алфавита, на экран.

Решение. В цикле проверим вхождение всех элементов базового типа и выводим те, которые входят в множество. var zn:set of 'A'..'z'; i:char;

begin for i:='A' to 'Z' do

if i in zn then write(i,' '); for i:='a' to 'z' do

if i in zn then write(i,' ');

Задача 3. Написать программу, которая в заданном слове, состоящем из строчных букв, определяет составляющие его буквы, глухие и звонкие согласные, затем все согласные и все гласные буквы. Решение.

type setchar = set of char;

ALF:string='абвгдеёжзийклмнопрстуфхцчшщъыьэюя'; var s:string;

for i:=1 to length(ALF) do if ALF[i] in mn then write(ALF[i],' '); writeln; end;

begin write('Введите русское слово '); readln(s);

gla:=buk-(sog+[V,V]); print('слово состоит из букв; ',buk); print('гласные буквы: ',gla); print('согласные буквы: ',sog); print('глухие согласные: ',mgl); print('звонкие согласные; ',mzv); end.

Задача 4. Заданы два слова. Определить буквы, которые не являются общими для обоих слов.

Решение. Образуем множества, содержащие буквы первого и второго слова. Затем найдем разности первого и второго, второго и первого множеств. Их объединение даст ответ.

type setchar=set of char;

begin for i:=1 to length(ALF) do

if ALF[i] in mn then write(ALF[i],' '); writeln; end;

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

begin write('Введите два русских слова, разделив их нажатием клавиши Enter '); readln(s 1);readln(s2); ms1:=[]; ms2:=[]; for i:=1 to length(sl) do ms1:=ms1+[s1[i]]; < множество букв второго слова>for i:=1 to length(s2) do ms2:=ms2+[s2[i]]; g1:=ms1-ms2; g2:=ms2-ms1; print(g1+g2); end.

Задача 5. Написать программу для нахождения простых чисел с помощью «решета Эратосфена». Решение.

1. Поместим все числа между 2 и n (n<=255) в решето.

2. Выберем из решета наименьшее из чисел.

3. Поместим это число среди простых.

4. Переберем и вынем из решета все числа, кратные данному.

5. Если решето не пустое, то повторим шаги 2 - 5. const n=255; var interval,

begin interval:=[2..n]; prost:=[]; next:=2;

repeat while not (next in interval) do next:=succ(next); prost: =pro st+[next]; c:=2*next-1; j:=next; while j

begin interval:=interval-[j]; j:=j=c; end; until interval=[]; end.

Задача 6. Натуральные числа вводятся с клавиатуры до тех пор, пока не будет введено число нуль (признак окончания ввода). Написать программу для определения цифры, которая встречается во всех введенных числах.

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

if p=1 then begin s:=s1;p:=0; end else s:=s*s1; read(a);

for a:=0 to 9 do if a in s then write(a,' ');

15. Тип данных запись

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

Решение. Сведения об автовладельцах представим массивом записей. Исходные данные вводятся с клавиатуры. Работа с массивом записей аналогична работе с одномерным массивом.

writeln('Введите ',n,' автовладельцев'); for i:=1 to n do begin v[i].nomer:=i;

writeln('автовладелец номер ',v[i].nomer); write('Фамилия? ');readln(v[i].fio); write('марка ? ');readln(v[i].marka); write('адрес? ');readln(v[i].adres);

write('Какая марка вас интересует? ');

for i:=1 to n do if v[i].marka=s

then begin with v[i] do writeln(nomer,' ',marka,' ',fio,' ',adres); k:=k+1;

write('Количество владельцев марки ',s,'=',k);

Таким образом, представлены методики решения по пяти из девятнадцати выделенных классов задач:

11. Данные типа string.

12. Процедуры и функции.

14. Тип данных множество.

15. Тип данных запись.

В следующей статье мы продолжим знакомство с методикой быстрого обучения программированию на основе изучения классов задач. Будут рассмотрены методики по следующим двум из девятнадцати выделенных классов задач:

17. Организация работы с модулями.

1. Аляев Ю.А. Алгоритмизация и языки программирования Pascal, C++, Visual Basic / Ю.А. Аляев, О.А. Козлов. М.: Финансы и статистика, 2002, 2004, 2007. 320 с.

2. Аляев Ю.А. Практикум по алгоритмизации и программированию на языке Паскаль / Ю.А. Аляев, В.П. Гладков, О.А. Козлов. М.: Финансы и статистика, 2004, 2007. 528 с.

3. Аляев Ю.А. Методика быстрого обучения программированию на основе изучения классов задач (1-3) // Образовательные ресурсы и технологии. 2015'1(9). С. 3-14. URL: http://www.muiv.ru/vestnik/pdf/pp/ot_2015_1_3-14.pdf

4. Аляев Ю.А. Методика быстрого обучения программированию на основе изучения классов задач (4-5) // Образовательные ресурсы и технологии. 2015'2(10). С. 3-16. URL: http://www.muiv.ru/vestnik/pdf/pp/ot_2015_2_3 - 16.pdf

5. Аляев Ю.А. Методика быстрого обучения программированию на основе изучения классов задач (6-7) // Образовательные ресурсы и технологии. 2015'3(11). С. 3-20. URL: http://www.muiv.ru/vestnik/pdf/pp/ot_2015_003_020.pdf

6. Аляев Ю.А. Методика быстрого обучения программированию на основе изучения классов задач (8-10) // Образовательные ресурсы и технологии. 2015'4(12). С. 26-43. URL: http://www.muiv.ru/vestnik/pdf/pp/ot_2015_4_026-043.pdf

Methods of the quick education to programming on base of the study of the classes of the problems (11-15)

Yuri Alexandrovich Alyaev, assistant professor, assistant professor of the pulpit of software of the computing machinery and automated systems, Perm military institute of internal troops of the MIA of Russia,

Is offered methods of the quick education to programming on base of the study of the classes of the problems, designed and using in practice in process of the education to programming student high school.

The Keywords: algorithm, program, programming language Pascal, array, procedures and functions, recursion, set, record

JavaScript Algorithms and Data Structures: Recursive Staircase

Recursive Staircase is a problem where you have to determine the number of ways to reach the top of a staircase, given that you can only take 1 or 2 steps at a time. Learn how to implement Recursive Staircase in JavaScript.

The Problem

There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 or 2 stairs at a time. Count the number of ways, the person can reach the top.

The Solution

  • Brute Force Recursive Solution - Time: O(2^n); Space: O(1)
  • Recursive Solution With Memoization - Time: O(n); Space: O(n)
  • Dynamic Programming Solution - Time: O(n); Space: O(n)
  • Iterative Solution - Time: O(n); Space: O(1)

References

  • On YouTube by Gayle Laakmann McDowell
  • GeeksForGeeks

#javascript #algorithms #datastructures

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *