Мне бы хватило – я просто вашу программу в C++ засунул, с небольшими доработками:
#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
int main(int argc, char* argv[])
{
// max произведение
int max(0);
// рабочий вектор и вектор результатов
vector<char> p = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, result;
// перестановки 9 цифр:
while (next_permutation(p.begin(), p.end())) {
// первое трёхзначное число :
int n1 = p[0] * 100 + p[1] * 10 + p[2];
// второе трёхзначное число :
int n2 = p[3] * 100 + p[4] * 10 + p[5];
// третье трёхзначное число :
int n3 = p[6] * 100 + p[7] * 10 + p[8];
// их произведение :
int m = n1 * n2 * n3;
// больше максимального ?
if (m >= max) {
max = m;
result = p;
}
}
// печатаем ответ
cout << "Max product = " << max << endl;
copy(result.begin(), result.end(), ostream_iterator<int>(cout, " "));
system("pause");
return 0;
}
Мне кажется, это не тот пример, который для обучения подходит. Безусловно, Питон тут выглядит получше Паскаля, но такие алгоритмы можно на Питоне писать только после того, как Вы объясните работу алгоритма permutations, и расскажете, как устроен и работает range. Но это так, на правах личного мнения. Я понимаю, что Питон удобен, лаконичен и красив, но числодробительные алгоритмы – явно не его конёк.
Решить задачу - значит придумать алгоритм её решения.
Понятно, что его можно записать на любом языке программирования, а на языке C++ он будет работать быстрее всего.
В данном случае решение и на Питоне, и на C++ одно и то же, поскольку реализует один и тот же алгоритм.
Это не новое решение. Но на Питоне исходный код выглядит гораздо проще и понятнее. Это важно, когда мы имеем в виду обучение программированию.
Что касается задачи, то она безусловно учебная, так как публиковалась в журнале “Квант” для школьников.
Естественно, предполагалось, что её будут решать не на компьютере, а на бумаге. Но как её можно решить иначе, чем перебором? А переборные задачи - это задачи для компьютера, а не для людей.
На мой взгляд, именно эта задача хорошо показывает, для чего нужен компьютер.
Перестановки изучают в детском саду и в младших классах средней школы. Как и некоторые другие комбинаторные объекты. Правда, при этом обходятся без “научных” терминов, но это сути дела не меняет.
Функция range выдаёт арифметическую последовательность, которая известна ученикам пятого класса.
Работу алгоритма permutations объяснять не обязательно. Как известно, придумано много алгоритмов для генерирования перестановок. Какой именно реализован в Питоне я не знаю, хотя и догадываюсь. Мешает ли мне это “незнание” решить задачу? - Ничуть!
В бесполезной книге “Полезное программирование. Уникальное руководство к действию” вы можете прочитать, как автор отбирает кандидатов на работу, предлагая им написать программу для пузырьковой сортировки.
Точно такой же ерундой занимаются и в школе. Вместо программирования изучают во всех подробностях тонкости и хитрости языка паскаль. Нам нужен паскаль или умение решать задачи?
Не надо копать яму детским совком! Уже давно изобрели экскаваторы - большие для больших ям, маленькие - для маленьких.
И в Питоне, и в паскале имеются встроенные функции и методы для сортировки последовательностей.
Но можно пару часов изучать никому ненужную пузырьковую сортировку.
Хотелось бы видеть на форуме больше реальных проектов, а пока он больше напоминает книгу жалоб и предложений.
А скажите - вот, мы после этого, разумеется, напишем в PascalABC.NET стандартную функцию NextPermutation. Изменится ли после этого ваше сравнение Питона и Паскаля?
Ув. Валерий, мне кажется, что решить задачу – это всё-таки сначала подобрать подходящие инструменты, а потом с учётом этих инструментов написать алгоритм и реализовать его для выбранного инстументария.
Приведённый пример смущает меня тем, что выбранный Вами для решения задачи инструмент работает в сотни раз медленней, чем это могло бы быть. В действительности это не важно, мы же алгоритмы изучаем, а не языки, но «осадочек» остался – в таких задачах Питон как раз и выступает в роли детского совочка.
Хотите показать красоту и удобство Питона? Напишите какие-нибудь действительно интересные проекты – например, собрать в архив все файлы с текстами программ из какой-нибудь папки, засунуть в архив и отправить на указанный электронный адрес. Чем не реальный проект? Уверен, тут Питон всех победит.
Нет, тогда получается, что мы хотим решить детскую задачу и выбираем для этого C++, который быстрее.
Здесь ведь речь про обучение программированию, а не про решение конкретных задач.
Ваш пример с C++ основан на том же самом алгоритме, что и на Питоне.
Выигрыш в скорости очевиден, но ничего не доказывает, ведь мы и не стремились решить задачу за 2 миллисекунды. Наверняка алгоритм можно улучшить, но зачем? В принципе, задачу можно вообще решить методом грубой силы, то есть полным перебором, но он ничему новому здесь не научит.
Суть в том, что данная задача красиво и просто решается комбинаторным путём.
В Питоне для этого есть соответствующие методы, а в паскале их нет.
В C++ есть всё, но я очень надеюсь, что хотя бы в школе его никогда изучать не будут.
Данный пример как раз и показывает, что Питон очень хорош для решения многих несложных, “школьных” задач и при этом не требует применения сложных конструкций и напряжения мыслей.
Важна ли здесь скорость вычислений? - Если речь идёт о миллисекундах и даже секундах, то не важна.
Гораздо важнее простота алгоритма и его реализации.
Под детским совочком я понимаю низкоуровневое программирование, которым как раз и отличается C++. За счёт этого и достигается более высокая скорость работы. Если мы будем писать на ассемблере, то скорость ещё вырастет. Комбинаторный пример демонстрирует, что Питон значительно более высокоуровневый язык программирования, чем актуальный паскаль, поскольку он не заставляет писать низкоуровневые функции, чтобы генерировать перестановки. Это значит, что программу можно строить быстрее и большими кусками. А ссылки, указатели, ячейки памяти и прочая машинная мелочь - это и есть детский совочек, которым мы ковыряем элементарный код.
В Питоне позволительно подключать быстрые модули, написанные на языке С. Естественно, когда в этом есть необходимость. Зачем это нужно знать школьникам? Быстрее чем за 10 лет они всё равно не закончат…
Да и вообще я имел в виду как раз алгоритмическое мышление, а не изучение того или иного языка программирования. Большинство выпускников школы забудут его через год. А правильное мышление останется с ними на всю жизнь. Научившись раз плавать или ездить на велосипеде, разучиться уже невозможно.
То есть алгоритмическое мышление - это и есть цель обучения программированию, а язык программирования для этого нужно выбирать такой, чтобы не изучать его до последнего класса, когда уже не останется времени что-либо решать. Что легче и быстрее выучить? - Наверняка Питон или паскаль, но никак не С++.
Предложенные Вами примеры наверное подтвердят красоту Питона, но лично я не люблю такие задачи.
Да и Питон я рассматриваю здесь только как учебный язык. Он для этого очень хорош… Впрочем, я уже об этом писал.
Мне нравится паскаль (наш!). Это язык с богатыми возможностями, который вполне годится для обучения программированию в школе. Поскольку язык активно развивается, то сравнение его с Питоном должно показать, что можно было бы сделать, чтобы паскаль стал ещё лучше и ни в чём не уступал Питону.
Безусловно, модуль с комбинаторными методами/функциями заметно усилил бы возможности паскаля по части решения разного рода задач.
К сожалению, я не вижу практически никакого интереса к паскалю. Для решения задач он почти не применяется. Это и заставляет задуматься: а нужно ли и дальше развивать паскаль, тратя на это время и силы, или просто взять Питон в готовом виде. Он развивается сам собой, а нам и делать ничего не нужно. Конечно, такой подход можно охарактеризовать словами из юмористического рассказа Чехова “лопай, что дают”, но лопают же пиццу вместо пирожков. Почему и в обучении программированию не пойти этим же путём?
Увы, в России никогда не ценили хорошее своё, предпочитая не очень хорошее, но чужое…
Сейчас проходит Чемпионат мира по дартсу 2016 года, и я хочу предложить вам задачку на эту тему.
Придумал сам, так что, если что-нибудь соврал, то аккуратно поправьте меня.
Круглая мишень разделена на 20 равных секторов.
В каждой игре нужно набрать быстрее соперника 501 очко. За 1 подход игрок может бросить 3 дротика. Желательно попасть ими в мишень. При попадании непосредственно в сектор (сектора окрашены в чёрный и белый цвет попеременно) игроку начисляется столько очков, сколько написано рядом с сектором. Если присмотреться к рисунку, то можно разглядеть, что по периферии круга расставлены числа от 1 до 20.
Таким образом, одним броском можно выбить все числа 1…20. Но это ещё не всё! При попадании во внешнее зелёно-красное кольцо очки соответствующего сектора удваиваются, а при попадании во внутреннее зелёно-красное кольцо очки утраиваются. Но и это ещё не всё! Центральный красный глазок даёт 50 очков, а зелёное кольцо вокруг него – 25.
Легко подсчитать, что тремя дротиками можно выбить минимум 0 очков, а максимум – 180.
В начале игры важно и выгодно набирать по 180 очков за раз, что особенно ценится игроками и зрителями. Это магическое число можно встретить на многих картинках, посвящённых этой замечательной и броской игре.
В конце игры ситуация другая. Так как игроку нужно набрать точно 501, ни больше ни меньше, то нужно чётко распределить дротики по секторам, чтобы получить нужную сумму.
Может показаться, что тремя дротиками можно выбить любую сумму от 1 до 180, но это не так. Некоторые суммы тремя дротиками выбить невозможно. Какие? – Вот в чём вопрос этой задачи.
Решение на Питоне будет представлено после Нового года, с которым я всех форумчан и поздравляю!
[quote=“JediKnight, post:46, topic:398”]
В минут 10 задачка. Вот если бы чисел в дартсе было эдак 1000-10000, и время парой секунд ограничено…
[/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.
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)
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 выдаёт, надо многократно запускать.
[quote=“JediKnight, post:51, topic:398”]
А можно вкратце суть алгоритма? Что-то не вкурю…
[/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 бросков.
Моя основная цель - 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)
*******************************************************
С НОВЫМ ГОДОМ, ДОРОГИЕ ТОВАРИЩИ!
*******************************************************
Ну, на Питоне можно и всё в виде множеств – вроде как короче выйдет по записи. А то, что алгоритм 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)
Не обижайтесь. Задачки у Вас хорошие и подход хороший. Ну просто действительно - в топике для Паскаля Вы полностью переключились на обсуждение Питона. Питон - отличный язык - никто не спорит.
Ну и давайте заведем ветку на другом подфоруме нашего форума - будем обсуждать там. Потому что журнал Смекайлик - его формат явно больше PascalABC.NET.
Программа для решения этой задачи не обязательна, но если всё-таки очень хочется, то можно воспользоваться 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
Опять таки шесть строк, и все имеют вид полюсов разных цветов и пояса из четырёх одинаковых граней между ними. но заметим. что куб у которого спереди красный, сзади синий. а посередине зелёный можно перевернуть и тогда он будет уже спереди синим, сзади красным, а посередине (где четыре одинаковых грани) всё ещё зелёным. Таким образом каждый возможный куб перечислен по два раза, а всего их три уникальных.
Институт математики, механики и компьютерных наук ЮФУ, 2005–2021