Задачки для разминки. (Простенькие такие...)

Модератор: Модераторы разделов

frp
Сообщения: 1445
ОС: Debian Squeeze

Re: Задачки для разминки.

Сообщение frp »

eddy ну я же говорил что задача с подвохом и не такая простая как кажется. Я тоже умею решать квадратное уравнение (а мое уравнение таковым не является т.к. квадратное уравнение является уравнением вида ax^2+bx+c=0 где a!=0, а у меня может быть ситуация что a==0)
Если бы все было так просто то я бы не публиковал бы эту задачу.

Код: Выделить всё

./a.out 0 0 0

Два совпадающих действительных корня

Правильный ответ - корнями являются все действительные числа (вот именно к этому случаю и относился намек с utf8).

Код: Выделить всё

./a.out 0 0 5

Два совпадающих действительных корня

Правильный ответ - уравнение корней не имеет.

Код: Выделить всё

./a.out 0 3 6

Два разных действительных корня

Правильный ответ - 1 действительный корень.

drBatty писал(а):
19.03.2010 12:05
А решение простое
b*b - 4*a*c
и проверяем знак - 3 случая получается. В чём сложность?

В том, что случаев-то 6.
Спасибо сказали:
Аватара пользователя
drBatty
Сообщения: 8735
Статус: GPG ID: 4DFBD1D6 дом горит, козёл не видит...
ОС: Slackware-current
Контактная информация:

Re: Задачки для разминки.

Сообщение drBatty »

frp писал(а):
19.03.2010 13:41
В том, что случаев-то 6.

да, шесть. подразумевается, что мы уже написали программу для решения уравнений первой и нулевой степени...
которые имеют 1 или ноль корней соотв.
ну и шестой особый случай - тожедество "0 равно 0" - это вообще не уравнение ИМХО.
http://emulek.blogspot.ru/ Windows Must Die
Учебник по sed зеркало в github

Скоро придёт
Осень
Спасибо сказали:
frp
Сообщения: 1445
ОС: Debian Squeeze

Re: Задачки для разминки.

Сообщение frp »

drBatty писал(а):
19.03.2010 13:49
ну и шестой особый случай - тожедество "0 равно 0" - это вообще не уравнение ИМХО.

На acmp.ru в задаче "Квадратное уравнение" такой случай есть :)
Спасибо сказали:
Аватара пользователя
drBatty
Сообщения: 8735
Статус: GPG ID: 4DFBD1D6 дом горит, козёл не видит...
ОС: Slackware-current
Контактная информация:

Re: Задачки для разминки.

Сообщение drBatty »

frp писал(а):
19.03.2010 14:09
На acmp.ru в задаче "Квадратное уравнение" такой случай есть

и как это называется, и главное - как это согласуется с основной теоремой? это уравнение какой степени?
http://emulek.blogspot.ru/ Windows Must Die
Учебник по sed зеркало в github

Скоро придёт
Осень
Спасибо сказали:
NickLion
Сообщения: 3408
Статус: аватар-невидимка
ОС: openSUSE Tumbleweed x86_64

Re: Задачки для разминки.

Сообщение NickLion »

В исходной задаче не сказано, что уравнение квадратное, поэтому всё верно - вариантов 6. Если же мы говорим, что уравнение квадратное, то это значит, что a!=0 (см. определение кв. ур-я).
Спасибо сказали:
Аватара пользователя
Fangelion
Сообщения: 112
ОС: Debian GNU/Linux

Re: Задачки для разминки.

Сообщение Fangelion »

Subj писал(а):
22.12.2009 14:19
Тогда вот такая задачка

Есть некий текст на входе (размер неограничен). Необходимо его отредактировать по аналогии с примером:
Было:
Какой же Новый год без ёлки? Пушистая, нарядная и яркая ёлочка – незаменимый атрибут праздничного настроения и новогоднего веселья.


Должно стать както вот так:
Какой же Новый год
без ёлки? Пушистая, нарядная
и яркая ёлочка – незаменимый атрибут
праздничного настроения и новогоднего веселья.


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


Вот простое решение без гладкости. Код не красивый, написаный за 15 минут от нечего делать

Код: Выделить всё

[user@debian]:~/src$ cat txt
#!/bin/python
# -*- coding: utf-8 -*-
import string
txt="Какой же Новый год без ёлки? Пушистая, нарядная и яркая ёлочка – незаменимый атрибут праздничного настроения и новогоднего веселья."
w=1
txt = txt.split(" ")
while len(txt):
    string = ""
    if len(txt)/2 > w-2:
        for i in range(w-1):
            string = string+" "+txt.pop(0)
        w = w + 1
    else:
        string = " "+" ".join(txt)
        txt = []
    print string
[user@debian]:~/src$ py txt

 Какой
 же Новый
 год без ёлки?
 Пушистая, нарядная и яркая
 ёлочка – незаменимый атрибут праздничного настроения и новогоднего веселья.
[user@debian]:~/src$


Ой. лесенка не по символам а по словам.
Спасибо сказали:
Аватара пользователя
drBatty
Сообщения: 8735
Статус: GPG ID: 4DFBD1D6 дом горит, козёл не видит...
ОС: Slackware-current
Контактная информация:

Re: Задачки для разминки.

Сообщение drBatty »

Fangelion писал(а):
20.03.2010 11:58
Вот простое решение без гладкости. Код не красивый, написаный за 15 минут от нечего делать

не понял условия: если в строке n у нас m слов, то в строке n+1 будет ровно m+1 слов. Причём тут гладкость? разбиение строк не представляет собой никакой сложности: достаточно перед буквой поставить '\n'. Код на sed можно написать за пять минут, но видимо я чего-то недопонял.
http://emulek.blogspot.ru/ Windows Must Die
Учебник по sed зеркало в github

Скоро придёт
Осень
Спасибо сказали:
Аватара пользователя
Fangelion
Сообщения: 112
ОС: Debian GNU/Linux

Re: Задачки для разминки.

Сообщение Fangelion »

drBatty писал(а):
20.03.2010 12:53
Fangelion писал(а):
20.03.2010 11:58
Вот простое решение без гладкости. Код не красивый, написаный за 15 минут от нечего делать

не понял условия: если в строке n у нас m слов, то в строке n+1 будет ровно m+1 слов. Причём тут гладкость? разбиение строк не представляет собой никакой сложности: достаточно перед буквой поставить '\n'. Код на sed можно написать за пять минут, но видимо я чего-то недопонял.

Я условие перечитал еще пару раз и понял
Задача:
разбить фразу по словам, при том, что количество букв в следующей строке всегда будет больше чем в предидущей. При этом "гладкость" обозначает равномерное распределение букв по строкам. т.е. примерно как у меня без последней строки.
Спасибо сказали:
Аватара пользователя
/dev/random
Администратор
Сообщения: 5282
ОС: Gentoo

Re: Задачки для разминки.

Сообщение /dev/random »

drBatty писал(а):
20.03.2010 12:53
не понял условия: если в строке n у нас m слов, то в строке n+1 будет ровно m+1 слов.

Во-первых, длина строки считается по буквам. Во-вторых, при таком подходе на последнюю строку может остаться слишком мало букв, и условие выполняться не будет. А если просто присобачить эту короткую строку к предпоследней, то условие выполняться будет, но решение не всегда будет оптимальным.
Спасибо сказали:
Аватара пользователя
drBatty
Сообщения: 8735
Статус: GPG ID: 4DFBD1D6 дом горит, козёл не видит...
ОС: Slackware-current
Контактная информация:

Re: Задачки для разминки.

Сообщение drBatty »

Fangelion
/dev/random
а, точно. действительно, с моим подходом получается ерунда:

Код: Выделить всё

В
лесу                   родилась
ёлочка, в лесу
она росла, зимой и

интересно, надо подумать...
http://emulek.blogspot.ru/ Windows Must Die
Учебник по sed зеркало в github

Скоро придёт
Осень
Спасибо сказали:
Аватара пользователя
Crazy
Сообщения: 862
Статус: Адепт Дзен.
ОС: Mint, Win7.

Re: Задачки для разминки.

Сообщение Crazy »

drBatty писал(а):
19.03.2010 12:05
Crazy писал(а):
19.03.2010 11:48
Учим основную теорему алгебры, полином степени n имеет не более n корней.

ага. подучите.
РОВНО n корней!
в данном случае всегда 2шт.

В области комплексных чисел да, в области вещественных нет.

Desipere in loco
Спасибо сказали:
Аватара пользователя
Fangelion
Сообщения: 112
ОС: Debian GNU/Linux

Re: Задачки для разминки.

Сообщение Fangelion »

/dev/random писал(а):
20.03.2010 13:07
Во-первых, длина строки считается по буквам. Во-вторых, при таком подходе на последнюю строку может остаться слишком мало букв, и условие выполняться не будет. А если просто присобачить эту короткую строку к предпоследней, то условие выполняться будет, но решение не всегда будет оптимальным.

Что и получилось у меня. Кстати может предусмотреть количество пробелов стоящих друг за другом?
Спасибо сказали:
Аватара пользователя
drBatty
Сообщения: 8735
Статус: GPG ID: 4DFBD1D6 дом горит, козёл не видит...
ОС: Slackware-current
Контактная информация:

Re: Задачки для разминки.

Сообщение drBatty »

Crazy писал(а):
20.03.2010 13:31
В области комплексных чисел да, в области вещественных нет.

извращаясь над областями можно добиться самых разных результатов:
например 2*2=? неразрешимо. В области чисел кратных 7и. В изначальном условии разве что-то было про области?
http://emulek.blogspot.ru/ Windows Must Die
Учебник по sed зеркало в github

Скоро придёт
Осень
Спасибо сказали:
Аватара пользователя
t.t
Бывший модератор
Сообщения: 7390
Статус: думающий о вечном
ОС: Debian, LMDE

Re: Задачки для разминки.

Сообщение t.t »

frp писал(а):
19.03.2010 09:38
Простая задачка: найдите количество корней уравнения ax^2+bx+c=0. Ораничения: дано числа a,b,c которые влезают в double. Дискриминант тоже обязательно влезает в double.

Выводить результат на консоль в любом понятном формате (можно словами в utf-8, но для обычных чисел все-таки предпочтительнее выводить их нормальным способом.)

Выложите здесь исходник.
И не стоит говорить что это простая задача... Даже если вы ее делали вместо hello world. Всеравно выложите.

Намек. Про utf8 я не по приколу написал :)
Если имеется ввиду "школьный" подсчёт, т.е. количество действительных корней, причём кратный корень считается одним корнем а не двумя, то вот "хакерский" вариант:

Код: Выделить всё

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
  if(argc != 3)
    return 1;
  double d = atoi(argv[1])^2 - 4*atoi(argv[0])*atoi(argv[2]);
  char c = (!argv[0]);
  if(c)
    c = (argv[1]!=0);
  else
    c += (d>0)+(d>=0);
  return putchar('0'+c) == EOF;
}
(:
¡иɯʎdʞ ин ʞɐʞ 'ɐнɔɐdʞǝdu qнεиж
Спасибо сказали:
Аватара пользователя
Crazy
Сообщения: 862
Статус: Адепт Дзен.
ОС: Mint, Win7.

Re: Задачки для разминки.

Сообщение Crazy »

argv[0] не содержит ли имя программы?
понял в чем прикол

Desipere in loco
Спасибо сказали:
Аватара пользователя
t.t
Бывший модератор
Сообщения: 7390
Статус: думающий о вечном
ОС: Debian, LMDE

Re: Задачки для разминки.

Сообщение t.t »

Crazy писал(а):
07.06.2010 22:13
argv[0] не содержит ли имя программы?
понял в чем прикол
А в чём? Я действительно на единичку промахнулся.
¡иɯʎdʞ ин ʞɐʞ 'ɐнɔɐdʞǝdu qнεиж
Спасибо сказали:
Аватара пользователя
diesel
Бывший модератор
Сообщения: 5989
ОС: OS X, openSuSE, ROSA, Debian
Контактная информация:

Re: Задачки для разминки.

Сообщение diesel »

iУведомление от модератора
Обсуждение математической составляющей переехало: Размышления о корнях уравнений :)
Спасибо сказали:
frp
Сообщения: 1445
ОС: Debian Squeeze

Re: Задачки для разминки.

Сообщение frp »

Кагбе не по линуксу, но все же:

Код: Выделить всё

.model tiny
.code
org 100h
start:
mov ah,9
mov dx,OFFSET Msg; выводим Msg
int 21h
mov ax,ds
dec ax
mov ds,ax
add dx,16
mov ah,9
int 21h; выводится опять Msg
ret
Msg DB 'Hello World',13,10,'$'
end start

(компилируется MASM, могу переделать под TASM, при компиляции надо генерировать .com).
Задача: объяснить, почему во второй раз тоже выводится Msg.
PS. Задача очень простая, но все же я знаю очень много людей, знакомых с ассемблером, но не способных ее решить.
Спасибо сказали:
frp
Сообщения: 1445
ОС: Debian Squeeze

Re: Задачки для разминки.

Сообщение frp »

UPD. И еще, объяснить, почему на 100% аналогичный пример, переписанный с использованием int 80h для вывода и скомпилированный под linux, работать не будет.
И аналогично предыдущему, объяснить, почему не будет работать аналогичный пример, скомпилированный под linux, с использованием функций libc для вывода строк.
При правильном решении предыдущего вопроса, решение этих вопросов будет очевидным.

Если надо, приведу исходники этих самых переделанных под линукс (с int 80h и libc) вариантов.
Спасибо сказали:
watashiwa_daredeska
Бывший модератор
Сообщения: 4038
Статус: Искусственный интеллект (pre-alpha)
ОС: Debian GNU/Linux

Re: Задачки для разминки.

Сообщение watashiwa_daredeska »

frp писал(а):
01.10.2010 21:34
(компилируется MASM, могу переделать под TASM, при компиляции надо генерировать .com).
О, боже. Вы б ещё PDP-11 вспомнили. :)
Спасибо сказали:
NickLion
Сообщения: 3408
Статус: аватар-невидимка
ОС: openSUSE Tumbleweed x86_64

Re: Задачки для разминки.

Сообщение NickLion »

А что там думать. Сегментная модель реального режима DOS - сегмент имеет размер 64K, но начинается каждый сектор через 16 байт после предыдщего. Таким образом получается 20 битная адресация памяти. А в Linux (как и Windows) используется модель памяти flat.
Спасибо сказали:
frp
Сообщения: 1445
ОС: Debian Squeeze

Re: Задачки для разминки.

Сообщение frp »

NickLion писал(а):
03.10.2010 01:16
Сегментная модель реального режима DOS - сегмент имеет размер 64K, но начинается каждый сектор через 16 байт после предыдщего.

Правильно.
NickLion писал(а):
03.10.2010 01:16
А в Linux (как и Windows) используется модель памяти flat.

AFAIK сегментацию никто не запрещал. Только сегментация защищенного режима не имеет почти ничего общего с сегментацией реального режима.
watashiwa_darede... писал(а):
03.10.2010 00:58
О, боже. Вы б ещё PDP-11 вспомнили. :)

PDP-11 - давно мертвая и забытая архитектура, сейчас AFAIK никто не выпускает совместимые с PDP-11 компьютеры.
А реальный режим x86 очень даже нужен загрузчикописателям, а во многих случаях - и ядерщикам.
Спасибо сказали:
NickLion
Сообщения: 3408
Статус: аватар-невидимка
ОС: openSUSE Tumbleweed x86_64

Re: Задачки для разминки.

Сообщение NickLion »

frp писал(а):
03.10.2010 14:51
NickLion писал(а):
03.10.2010 01:16
А в Linux (как и Windows) используется модель памяти flat.

AFAIK сегментацию никто не запрещал. Только сегментация защищенного режима не имеет почти ничего общего с сегментацией реального режима.

Угу, совсем ничего общего. Сегментная модель защищённого режима основаная на таблицах сегментов (GDT, LDT, IDT) - они могут иметь разный размер и положение (в том числе пересекаться). И доступна таблица сегментов для изменения только из ring0, если память не подводит. Фактически же используется flat. Ну, там ещё есть страничная модель памяти.
Ну и на x86-64 сегментная модель была убрана (правда AMD её возродила в дань виртуальным машинам, а Intel предложил Intel VT, и AMD тоже сделали аналог - AMD-V так что могут в дальнейшем убрать снова).
Спасибо сказали:
watashiwa_daredeska
Бывший модератор
Сообщения: 4038
Статус: Искусственный интеллект (pre-alpha)
ОС: Debian GNU/Linux

Re: Задачки для разминки.

Сообщение watashiwa_daredeska »

frp писал(а):
03.10.2010 14:51
А реальный режим x86 очень даже нужен загрузчикописателям, а во многих случаях - и ядерщикам.
Ох, дофига на свете загрузчикописателей... Каждый линуксоид не только сам себе ядерщик, но и загручик пишет сам. На TASM. Или MASM. Ага. :)
Спасибо сказали:
frp
Сообщения: 1445
ОС: Debian Squeeze

Re: Задачки для разминки.

Сообщение frp »

watashiwa_darede... писал(а):
04.10.2010 20:17
Ох, дофига на свете загрузчикописателей... Каждый линуксоид не только сам себе ядерщик, но и загручик пишет сам.

Не каждый, я только привел аргумент почему сравнивать нужность PDP-11 и реального режима x86 некорректно.
watashiwa_darede... писал(а):
04.10.2010 20:17
На TASM. Или MASM.

Никто на TASM или MASM не пишет. Но пишут на GAS, NASM, YASM, FASM. Но отличия незначительны (в основном это синтаксис всяких объявлений и макроязык, ну и AT&T синтаксис у GAS).

PS. Никто не станет в здравом уме писать загрузчик на TASM как минимум из-за того, что он генерирует кучу мусора в конце обычного бинарника (com). Я пробовал - чтобы обычный Hello World уместился в отведенное ему пространство в MBR или бут-секторе дискеты приходилось при помощи hex-редактора с интегрированным дизассемблером выпиливать этот самый мусор. С MASM такого не было, но он не хочет генерировать com, у которого стартовое смещение не 100h, а 7c00h (это ограничение можно легко обойти). А NASM лишен обеих этих проблем.
Спасибо сказали:
watashiwa_daredeska
Бывший модератор
Сообщения: 4038
Статус: Искусственный интеллект (pre-alpha)
ОС: Debian GNU/Linux

Re: Задачки для разминки.

Сообщение watashiwa_daredeska »

frp писал(а):
04.10.2010 21:27
Никто не станет в здравом уме писать загрузчик
Этого достаточно. Всё, что дальше — лишнее :)

frp писал(а):
04.10.2010 21:27
я только привел аргумент почему сравнивать нужность PDP-11 и реального режима x86 некорректно.
Реальный режим x86 жив исключительно по недоразумению. По хорошему, он уже давно должен быть там же, где и PDP-11. Так что, в общем, корректно.
Спасибо сказали:
frp
Сообщения: 1445
ОС: Debian Squeeze

Re: Задачки для разминки.

Сообщение frp »

watashiwa_daredeska писал(а):
04.10.2010 22:59
frp писал(а):
04.10.2010 21:27
я только привел аргумент почему сравнивать нужность PDP-11 и реального режима x86 некорректно.
Реальный режим x86 жив исключительно по недоразумению. По хорошему, он уже давно должен быть там же, где и PDP-11. Так что, в общем, корректно.

По хорошему, архитектура x86 в ее сегодняшнем виде (в том числе и x86-64) должна быть там же где и PDP-11 (хотя, если ее немного перепилить, выпилить рудименты, выпилить реальный режим ... :) ). А в идеале там же должны быть все CISC-архитектуры.
Спасибо сказали:
Аватара пользователя
Crazy
Сообщения: 862
Статус: Адепт Дзен.
ОС: Mint, Win7.

Re: Задачки для разминки.

Сообщение Crazy »

frp писал(а):
04.10.2010 21:27
но он не хочет генерировать com, у которого стартовое смещение не 100h, а 7c00h (это ограничение можно легко обойти)

MASM32 генерит.

Desipere in loco
Спасибо сказали:
Аватара пользователя
Olej
Сообщения: 659
ОС: Fedora, Mint, Debian, QNX
Контактная информация:

Re: Задачки для разминки.

Сообщение Olej »

Отличная идея ... была когда-то: "Задачки для разминки". :drinks:

И даже (или "ещё лучше") не в "Программирование для начинающих", а вообще в разделе по программированию : красивые и компактные задачи - это как этюды для пианиста... :rolleyes:

Только заболтали тему...
Вот как бывает, когда сообщения в форум пишут только для того, чтобы выставиться: какой я, якобы, умный (... самому себе кажусь :wacko: ).
А не для того, чтобы теме соответствовать и код писать и обсуждать.

Я хочу предложить, попробовать восстановить тему ... вписать сюда интересные (не самые примитивные) задачки, которые мне попались за несколько последних лет...
Ну, ... и при одном уточнении: если у пианиста показателем техники выполнения этюда есть темп, скорость, то у программиста при выполнении этюда (это же не проект) критерием должна быть ... краткость, компактность - как можно короче код наш девиз! :drinks:

Olej писал(а):
29.01.2016 13:47
как можно короче код наш девиз! :drinks:


№1 : Известно, что правильная рациональная дробь N / M ( N < M ) в десятичной записи может давать либо конечную запись ( 2 / 5 = 0.4 ), либо периодическую запись ( 1 / 3 = 0.(3) ). Рациональная дробь не может производить иррациональное значение (с непериодической десятичной записью, как, например, SQRT( 2 ) ). Создайте программу преобразования рациональной дроби в позиционную запись. Примите во внимание, что период может начинаться не с 1-й цифры после запятой: 1 / 12 = 0.08(3). Чтобы задача не казалась слишком лёгкой, сделайте её для произвольной системы счисления, основание которой (не только 10) вводится как отдельный параметр, например в 2-чной системе 2 / 3 = 0.(10) = 1 * ½ + 0 * ¼ + ...
Спасибо сказали:
Аватара пользователя
Olej
Сообщения: 659
ОС: Fedora, Mint, Debian, QNX
Контактная информация:

Re: Задачки для разминки.

Сообщение Olej »

№2 : В обработке временных рядов, цифровой обработке сигналов и для других целей часто вычисляется среднее и дисперсия (и далее среднеквадратичное отклонение) числовой последовательности X[ i ]: mean = 1 / N * ∑( X[ i ] ), disp = 1 / N * ∑( ( X[ i ] - mean )2 ). Но прямое вычисление характеристик по математическим формулам требует 2-х проходов: сначала вычисление среднего, а затем уже — дисперсии. Самое худшее при этом, что нужно хранить в памяти задачи всю последовательность чисел, что при больших N неприемлемо. Напишите программу для вычисления среднего и дисперсии (массива для примера) в 1 проход, в потоке поступления входных чисел, без их хранения.

Эта задача имеет большую практическую ценность в цифровой обработке сигналов, статистике, обработке временных рядов...
Спасибо сказали:
Ответить