Журнал "Смекайлик"

Среда PascalABC.NET
#43

Нет, тогда получается, что мы хотим решить детскую задачу и выбираем для этого C++, который быстрее. Здесь ведь речь про обучение программированию, а не про решение конкретных задач. Ваш пример с C++ основан на том же самом алгоритме, что и на Питоне. Выигрыш в скорости очевиден, но ничего не доказывает, ведь мы и не стремились решить задачу за 2 миллисекунды. Наверняка алгоритм можно улучшить, но зачем? В принципе, задачу можно вообще решить методом грубой силы, то есть полным перебором, но он ничему новому здесь не научит. Суть в том, что данная задача красиво и просто решается комбинаторным путём. В Питоне для этого есть соответствующие методы, а в паскале их нет. В C++ есть всё, но я очень надеюсь, что хотя бы в школе его никогда изучать не будут.

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

Важна ли здесь скорость вычислений? - Если речь идёт о миллисекундах и даже секундах, то не важна. Гораздо важнее простота алгоритма и его реализации.

Под детским совочком я понимаю низкоуровневое программирование, которым как раз и отличается C++. За счёт этого и достигается более высокая скорость работы. Если мы будем писать на ассемблере, то скорость ещё вырастет. Комбинаторный пример демонстрирует, что Питон значительно более высокоуровневый язык программирования, чем актуальный паскаль, поскольку он не заставляет писать низкоуровневые функции, чтобы генерировать перестановки. Это значит, что программу можно строить быстрее и большими кусками. А ссылки, указатели, ячейки памяти и прочая машинная мелочь - это и есть детский совочек, которым мы ковыряем элементарный код.

В Питоне позволительно подключать быстрые модули, написанные на языке С. Естественно, когда в этом есть необходимость. Зачем это нужно знать школьникам? Быстрее чем за 10 лет они всё равно не закончат… Да и вообще я имел в виду как раз алгоритмическое мышление, а не изучение того или иного языка программирования. Большинство выпускников школы забудут его через год. А правильное мышление останется с ними на всю жизнь. Научившись раз плавать или ездить на велосипеде, разучиться уже невозможно. То есть алгоритмическое мышление - это и есть цель обучения программированию, а язык программирования для этого нужно выбирать такой, чтобы не изучать его до последнего класса, когда уже не останется времени что-либо решать. Что легче и быстрее выучить? - Наверняка Питон или паскаль, но никак не С++.

Предложенные Вами примеры наверное подтвердят красоту Питона, но лично я не люблю такие задачи. Да и Питон я рассматриваю здесь только как учебный язык. Он для этого очень хорош… Впрочем, я уже об этом писал.

1 лайк
#44

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

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

К сожалению, я не вижу практически никакого интереса к паскалю. Для решения задач он почти не применяется. Это и заставляет задуматься: а нужно ли и дальше развивать паскаль, тратя на это время и силы, или просто взять Питон в готовом виде. Он развивается сам собой, а нам и делать ничего не нужно. Конечно, такой подход можно охарактеризовать словами из юмористического рассказа Чехова “лопай, что дают”, но лопают же пиццу вместо пирожков. Почему и в обучении программированию не пойти этим же путём?

Увы, в России никогда не ценили хорошее своё, предпочитая не очень хорошее, но чужое…

1 лайк
#45

Сейчас проходит Чемпионат мира по дартсу 2016 года, и я хочу предложить вам задачку на эту тему. Придумал сам, так что, если что-нибудь соврал, то аккуратно поправьте меня.

Круглая мишень разделена на 20 равных секторов.

В каждой игре нужно набрать быстрее соперника 501 очко. За 1 подход игрок может бросить 3 дротика. Желательно попасть ими в мишень. При попадании непосредственно в сектор (сектора окрашены в чёрный и белый цвет попеременно) игроку начисляется столько очков, сколько написано рядом с сектором. Если присмотреться к рисунку, то можно разглядеть, что по периферии круга расставлены числа от 1 до 20.

Дартс3.png3286×3202 979 KB

Таким образом, одним броском можно выбить все числа 1…20. Но это ещё не всё! При попадании во внешнее зелёно-красное кольцо очки соответствующего сектора удваиваются, а при попадании во внутреннее зелёно-красное кольцо очки утраиваются. Но и это ещё не всё! Центральный красный глазок даёт 50 очков, а зелёное кольцо вокруг него – 25.

Легко подсчитать, что тремя дротиками можно выбить минимум 0 очков, а максимум – 180.

В начале игры важно и выгодно набирать по 180 очков за раз, что особенно ценится игроками и зрителями. Это магическое число можно встретить на многих картинках, посвящённых этой замечательной и броской игре.

В конце игры ситуация другая. Так как игроку нужно набрать точно 501, ни больше ни меньше, то нужно чётко распределить дротики по секторам, чтобы получить нужную сумму.

Может показаться, что тремя дротиками можно выбить любую сумму от 1 до 180, но это не так. Некоторые суммы тремя дротиками выбить невозможно. Какие? – Вот в чём вопрос этой задачи.

Решение на Питоне будет представлено после Нового года, с которым я всех форумчан и поздравляю!

#46

В минут 10 задачка. Вот если бы чисел в дартсе было эдак 1000-10000, и время парой секунд ограничено… :smile:

#47

[quote=“JediKnight, post:46, topic:398”] В минут 10 задачка. Вот если бы чисел в дартсе было эдак 1000-10000, и время парой секунд ограничено… :smile: [/quote]Ну, тогда пришлось бы над алгоритмом думать, да и структуру данных подбирать. А так, «в лоб», что на Паскале, что на Питоне можно коротко записать. На Питоне красивее, в Паскале foreach тяжеловесный, требует тип указывать. Эффективность для обоих языков одинаково плохая – полсекунды, зато запись короткая.

begin
  var s := [25,50];
  for var x := 0 to 20 do
      s += [x,2*x,3*x];
  var mn := [1..180];
  foreach var x1 : integer in s do
    foreach var x2 : integer in s do
      foreach var x3 : integer in s do
        mn -= [x1+x2+x3];
  writeln(mn);
end.
#48

0.000122748 секунд, С++.

#include <iostream>
#include <bitset>
#include <chrono>

using namespace std;

const int VALUES_CIRCLE = 20;
const int POSSIBLE_SINGLE = VALUES_CIRCLE * 3;
const int POSSIBLE_THREE = POSSIBLE_SINGLE * 3;


int main()
{	
	auto first = std::chrono::high_resolution_clock::now();

	bitset<POSSIBLE_SINGLE + 1> possible_set;

	const int N = VALUES_CIRCLE;
	for (int i = 0; i <= N; i++)
	{
		possible_set.set(i);
		possible_set.set(i * 2);
		possible_set.set(i * 3);
	}
	possible_set.set(25);
	possible_set.set(50);

	bitset<POSSIBLE_THREE + 1> result_set;

	for (int i = 0; i <= POSSIBLE_SINGLE; i++)
	{
		if (!possible_set.test(i))
			continue;
		for (int j = i; j <= POSSIBLE_SINGLE; j++)
		{
			if (!possible_set.test(j))
			continue;
			for (int k = j; k <= POSSIBLE_SINGLE; k++)
			{
				if (!possible_set.test(k))
					continue;
				result_set.set(i + j + k);
			}
		}
	}

	auto second = std::chrono::high_resolution_clock::now();

	for (int i = 0; i <= POSSIBLE_THREE; i++)
	{
		if (!result_set.test(i))
			cout << i << " ";
	}
	cout << endl;

	double duration = (std::chrono::duration_cast<std::chrono::duration<double>>(second - first)).count();
	
	cout << "Duration(s): " << duration << endl;
	cin.get();
}
#49

Все-таки функциональное программирование - шедевр.

import Data.List
let possible = sort $ [25, 50] ++ ((nub.concat) [[x, x * 2, x * 3]| x<-[0..20]])
let combs = [(x, y, z) | x <- possible, y <- filter (\k -> k >= x) possible, z <- filter (\t -> t >= y) possible] 
let result = [0..180] \\ (nub $ map (\(a, b, c) -> a + b + c) combs)
#50

[quote=“JediKnight, post:48, topic:398”] 0.000122748 секунд, С++. [/quote] 0.00001969 секунд, PascalABC.Net :wink:

begin
  var A := ArrFill(181,Integer.MaxValue);
  for var i:=1 to 20 do
    begin
      A[i]:=1;A[2*i]:=1;A[3*i]:=1;
    end;
  A[25]:=1;A[50]:=1;
  for var i:=21 to 180 do
    for var j:=i-1 downto i div 2 do
      if A[i]>A[j]+A[i-j] then
          A[i]:=A[j]+A[i-j];
  for var i:=1 to 180 do
    if A[i]>3 then write(i,' ');
end.

Правда, у меня код на С++ вообще 0 выдаёт, надо многократно запускать.

#51

А можно вкратце суть алгоритма? Что-то не вкурю… :smile:

#52

[quote=“JediKnight, post:51, topic:398”] А можно вкратце суть алгоритма? Что-то не вкурю… :smile: [/quote]Массив А содержит минимальное число бросков для набора нужной суммы. Например, А[20] = 1, т.е. 20 можно выбить одним броском. А[87] = 2, т.к. 87 = 60 + 27 – минимум два броска нужны. Ну а дальше надо просто этот массив построить.

Пусть для некоторого n у нас уже вычислены значения A[1]…A[n-1]. Нужно найти A[n], для этого подбираем пару чисел i и n-i так, чтобы A[i] + A[n-i] были минимальными – то есть n очков набираем как i очков плюс n-i очков. Даже если i очков требовали двух бросков, то в A[i] будет сидеть 2, ну и в A[n-i] тогда должно быть 1. И так до 180, а потом смотрим, какие числа требуют больше 3 бросков.

#53

Может, Вы тогда перенесёте свою тему в другой форум? Раз основная цель - это PR Питона, то зачем нужно захламлять подфорум Паскаля?

#54

Моя основная цель - PR паскаля, чем никто не занимается, отсюда и отсутствие интереса к нему.

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

Всего хорошего, Admin!

================================================

Раз уж я обещал собственное решение на Питоне, то вот оно:smile:

# -*- coding: Windows-1251 -*-

from itertools import combinations_with_replacement
from timeit import default_timer as timer
start = timer()

# сектора, двойные сектора, тройные сектора  и BULL
score = [[i, i*2, i*3] for i in range(20+1)]
score = sum(score, [25, 50])
#print(score)

# избавляемся от повторов:
score = set(score)
#print(score)

# все суммы -->
all_sum = list(range(180+1))

for p in combinations_with_replacement(score, 3):
    sp = sum(p)
    if sp in all_sum:
        all_sum.remove(sp)

# печатаем невозможные суммы:
print("Невозможные суммы:", all_sum)


# печатаем время:
print(timer() - start)


             *******************************************************
             С НОВЫМ ГОДОМ, ДОРОГИЕ ТОВАРИЩИ!
            *******************************************************
#55

Ну, на Питоне можно и всё в виде множеств – вроде как короче выйдет по записи. А то, что алгоритм O(n3) вместо O(n2), да всякие мелкие «безобразия» – ну ничего, в ВУЗе переучим.

from itertools import product
A=set(range(20+1))
A=A|{x * 2 for x in A}|{x * 3 for x in A}|{25,50}
X=set(range(181)) - set(sum(l) for l in product(A, repeat=3))
print("Невозможные суммы:",X)

Да, и с Наступающим!

#56

Не обижайтесь. Задачки у Вас хорошие и подход хороший. Ну просто действительно - в топике для Паскаля Вы полностью переключились на обсуждение Питона. Питон - отличный язык - никто не спорит.

Ну и давайте заведем ветку на другом подфоруме нашего форума - будем обсуждать там. Потому что журнал Смекайлик - его формат явно больше PascalABC.NET.

1 лайк
#57

сайт не работает? в Смекайлике 1 и 3 есть проекты из книги Развивающее программирование. Занимательные проекты на Паскале или наоборот

#58

Программа для решения этой задачи не обязательна, но если всё-таки очень хочется, то можно воспользоваться GNU bash. Преимущество bash над другими языками в том, что не нужно ничего дополнительно запускать, поскольку все остальные программы запускаются из консоли, а в консоли по умолчанию в большинстве современных ОС по умолчанию в качестве интерпретатора командной строки запускается именно bash. Впрочем, без изменений эта команда работает и в zsh, втором по популярности интерпретаторе командной строки.

Представим себе куб смотрящий на нас гранью 1 (face 1, $f1), при этом сверху у нас будет вторая грань, справа третья, снизу четвёртая, слева пятая, а сзади шестая, то есть грани с f2 по f5 расположены по часовой стрелке. Цвета обозначим буквами r, g, b (red, green, blue) в честь раскраски пикселей дисплея.

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

Для каждой из восьми вершин задаём условие, согласно которому любые две из трёх сходящихся к ней граней должны быть одного цвета. Затем выводим раскраску.

Получается такой код:


for f1 in r; do
  for f2 in r g b; do
    for f3 in r g b; do
      for f4 in r g b; do
        for f5 in r g b; do
          for f6 in r g b; do
            if [[ ( $f3 == $f2 || $f3 == $f1 || $f2 == $f1 ) && \
                  ( $f4 == $f3 || $f4 == $f1 || $f3 == $f1 ) && \
                  ( $f5 == $f4 || $f5 == $f1 || $f4 == $f1 ) && \
                  ( $f2 == $f5 || $f2 == $f1 || $f5 == $f1 ) && \
                  ( $f3 == $f2 || $f3 == $f6 || $f2 == $f6 ) && \
                  ( $f4 == $f3 || $f4 == $f6 || $f3 == $f6 ) && \
                  ( $f5 == $f4 || $f5 == $f6 || $f4 == $f6 ) && \
                  ( $f2 == $f5 || $f2 == $f6 || $f5 == $f6 ) ]]; then
              echo $f1 $f2 $f3 $f4 $f5 $f6
            fi
          done
        done
      done
    done
  done
done | grep g | grep b

После перебора убираем те, где нет ни одной грани синего или ни одной грани зелёного цвета с помощью фильтров grep.

В результате получаем такой список:

r r g r b r
r r b r g r
r g r b r r
r g g g g b
r b r g r r
r b b b b g

В этом списке мы видим два явно уникальных варианта: r g g g g b и r b b b b g, но все остальные четыре варианта идентичны, в них грани f1 и f6 красного цвета, а остальные четыре двух других цветов перемежаемых красным, которые переходят один в другой при повороте вдоль оси проходящей через первую и шестую грань. То существует всего три уникальных раскраски куба, что и требовалось доказать.

Ещё один вариант такой:

for f1 in r g b; do
  for f2 in r g b; do
    for f3 in $f2; do
      for f4 in r g b; do
        for f5 in r g b; do
          for f6 in r g b; do
            if [[ ( $f3 == $f2 || $f3 == $f1 || $f2 == $f1 ) && \
                  ( $f4 == $f3 || $f4 == $f1 || $f3 == $f1 ) && \
                  ( $f5 == $f4 || $f5 == $f1 || $f4 == $f1 ) && \
                  ( $f2 == $f5 || $f2 == $f1 || $f5 == $f1 ) && \
                  ( $f3 == $f2 || $f3 == $f6 || $f2 == $f6 ) && \
                  ( $f4 == $f3 || $f4 == $f6 || $f3 == $f6 ) && \
                  ( $f5 == $f4 || $f5 == $f6 || $f4 == $f6 ) && \
                  ( $f2 == $f5 || $f2 == $f6 || $f5 == $f6 ) ]]; then
              echo $f1 $f2 $f3 $f4 $f5 $f6
            fi
          done
        done
      done
    done
  done
done | grep r | grep g | grep b

В этом случае мы предполагаем, что цвет граней 2 и 3 одинаковый, как в моём процитированном решении без компьютера, но поскольку цвет переднией грани может быть уже не красным, мы убираем это условие. В результате получается:

r g g g g b
r b b b b g
g r r r r b
g b b b b r
b r r r r g
b g g g g r

Опять таки шесть строк, и все имеют вид полюсов разных цветов и пояса из четырёх одинаковых граней между ними. но заметим. что куб у которого спереди красный, сзади синий. а посередине зелёный можно перевернуть и тогда он будет уже спереди синим, сзади красным, а посередине (где четыре одинаковых грани) всё ещё зелёным. Таким образом каждый возможный куб перечислен по два раза, а всего их три уникальных.