Получить из целых чисел заданное среднее

Здесь Вы можете найти или обсудить множество различных алгоритмов, их описаний, реализаций на VB и других языках.
oskolok_vatbI
Продвинутый пользователь
Продвинутый пользователь
Аватара пользователя
 
Сообщения: 112
Зарегистрирован: 07.07.2007 (Сб) 16:13
Откуда: г. Казань

Получить из целых чисел заданное среднее

Сообщение oskolok_vatbI » 07.12.2012 (Пт) 15:22

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

Изображение

Так генерирую целые числа:
Код: Выделить всё
Sub Macro1()
    Dim Value As Integer
    Dim sum As Integer
    Dim Middle As Double
    Dim uBnd As Integer
    Dim lBnd As Integer
   
    uBnd = 8
    lBnd = 3
   
    For j = 0 To 9
    Randomize
    Value = Int((uBnd - lBnd + 1) * Rnd + lBnd)
    sum = sum + Value
    Next j
   
    Middle = sum / 10
End Sub

Среднее значение среди полученных, по понятным причинам меняется хаотически. Как сделать постепенное приближение к нужной точности ? Выполнять этот цикл до тех пока значение Middle случайно не совпадет с нужной, не самый подходящий вариант, т.к. значений существенно больше 10.
Спасибо.

Proxy
Профессор VB наук
Профессор VB наук
Аватара пользователя
 
Сообщения: 2941
Зарегистрирован: 31.08.2007 (Пт) 4:41

Re: Получить из целых чисел заданное среднее

Сообщение Proxy » 07.12.2012 (Пт) 17:52

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

Ну а если после вычитания не укладывается в заданный диапазон, то разбросать оставшееся по произвольным точкам.
Follow the white rabbit.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Получить из целых чисел заданное среднее

Сообщение Хакер » 07.12.2012 (Пт) 18:22

Придат всем точкам значение, равное желаемому среднему.

Провести X итераций, суть в которых следующая: находится пара двух случайных точек, и генерируется случайное число k. К значению первой точки добавляется k, а от значения второй точки отнимается k.

k, естественно, генерируется при каждой итерации заново.
Значение X и диапазон случайных k выбирает по желанию.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

oskolok_vatbI
Продвинутый пользователь
Продвинутый пользователь
Аватара пользователя
 
Сообщения: 112
Зарегистрирован: 07.07.2007 (Сб) 16:13
Откуда: г. Казань

Re: Получить из целых чисел заданное среднее

Сообщение oskolok_vatbI » 07.12.2012 (Пт) 20:30

Спасибо.
Способ, предложенный Proxy я честно говоря не совсем понял.
Хакер, если пользоваться таким способом, не будет выполняться условие целочисленности значений. Или я чего-то не понимаю ?
Если присвоить всем элементам желаемое среднее, например 5.80 и вычитать из одного из них случайное число, не факт что оно станет целым, к тому же, могут остаться неохваченные операциями сложения-вычитания элементы.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Получить из целых чисел заданное среднее

Сообщение Хакер » 07.12.2012 (Пт) 20:39

А ты осознаёшь, что в общем случае задача вообще нерешаема?

Например, если среднее должно быть 5.8, а общее число точек = 11, то невозможно в принципе подобрать набор целых чисел.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

oskolok_vatbI
Продвинутый пользователь
Продвинутый пользователь
Аватара пользователя
 
Сообщения: 112
Зарегистрирован: 07.07.2007 (Сб) 16:13
Откуда: г. Казань

Re: Получить из целых чисел заданное среднее

Сообщение oskolok_vatbI » 07.12.2012 (Пт) 20:56

Проверил в экселе, согласен.
Однако с ростом количества точек будет расти возможность приблизиться к заданному среднему с необходимой точностью. Мне вполне достаточно второго знака. Т.е. будет ограничение по минимальному количеству данных, пусть 100 точек, это не критично.
Ведь в экселе, я могу долго и нудно подбирать значения, до тех пор пока итог меня не устроит. Наверное и тут возможно сделать так. Раскидать случайно диапазон, посчитать среднее и если в итоге среднее больше нужного, вычесть из величины случайной точки единицу, если меньше - единицу добавить. Мне кажется должно сработать.

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 07.12.2012 (Пт) 21:27

Генереиуем возрастающую последовательность, потом итерационно подравниваем под среднее и делаем random shuffle.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Получить из целых чисел заданное среднее

Сообщение Хакер » 07.12.2012 (Пт) 22:42

oskolok_vatbI писал(а):Однако с ростом количества точек будет расти возможность приблизиться к заданному среднему с необходимой точностью. Мне вполне достаточно второго знака. Т.е. будет ограничение по минимальному количеству данных, пусть 100 точек, это не критично.
Ведь в экселе, я могу долго и нудно подбирать значения, до тех пор пока итог меня не устроит. Наверное и тут возможно сделать так. Раскидать случайно диапазон, посчитать среднее и если в итоге среднее больше нужного, вычесть из величины случайной точки единицу, если меньше - единицу добавить. Мне кажется должно сработать.


Тогда ты сперва должен умножить необходимое среднее арифметическое число на количество точек. Полученный результат округлить до ближайшего целого числа. Это целое число, по методу, напоминающему алгоритм Брезенхема («как разделить 30 фишек на 20 группок, чтобы было примерно поровну?») присвоить значения всем точкам.

Потом по точкам пройтись уже описанными мною итерациями, которые будут брать пары и одной из точек увеличивать значение, а другой — уменьшать на ту же величину.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 07.12.2012 (Пт) 23:30

Хакер писал(а):Потом по точкам пройтись уже описанными мною итерациями

Мне кажется, что лучше брать последовательные точки, а в конце всё перемешать.

oskolok_vatbI
Продвинутый пользователь
Продвинутый пользователь
Аватара пользователя
 
Сообщения: 112
Зарегистрирован: 07.07.2007 (Сб) 16:13
Откуда: г. Казань

Re: Получить из целых чисел заданное среднее

Сообщение oskolok_vatbI » 08.12.2012 (Сб) 15:03

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

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Получить из целых чисел заданное среднее

Сообщение Хакер » 08.12.2012 (Сб) 15:05

Что такое точность?
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

oskolok_vatbI
Продвинутый пользователь
Продвинутый пользователь
Аватара пользователя
 
Сообщения: 112
Зарегистрирован: 07.07.2007 (Сб) 16:13
Откуда: г. Казань

Re: Получить из целых чисел заданное среднее

Сообщение oskolok_vatbI » 08.12.2012 (Сб) 16:15

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

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16473
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Получить из целых чисел заданное среднее

Сообщение Хакер » 08.12.2012 (Сб) 16:46

Ты вообще понял алгоритм? Похоже совсем не понял.

Последний итерационный этап никак ни в какую сторону не изменяет среднее значение. Он только привносит хаос в значения в определённой тобою степени.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

oskolok_vatbI
Продвинутый пользователь
Продвинутый пользователь
Аватара пользователя
 
Сообщения: 112
Зарегистрирован: 07.07.2007 (Сб) 16:13
Откуда: г. Казань

Re: Получить из целых чисел заданное среднее

Сообщение oskolok_vatbI » 19.12.2012 (Ср) 7:44

Снова здравствуйте.
Хакер, да. Действительно, я сначала не понял твоего алгоритма. Теперь я никак не пойму, как применить алгоритм Брезенхема для раскидывания значения по всем точкам. Все примеры, которые мне удалось найти, включая твою статью на этом форуме, посвящены рисованию окружностей и наклонных линий. Поэтому я сделал самым простым способом, который пришел в голову. Значение, полученное в ходе умножения необходимого среднего арифметического на количество точек я раскидываю в массив данных по кругу, а потом вношу немного "хаоса":
Код: Выделить всё
Option Explicit

Dim minPossibleValue As Integer            'Минимально возможное значение данных
Dim maxPossibleValue As Integer           'Максимально возможное значение данных
Dim NecessaryMiddleValue As Double     'Среднее значение, которое необходимо получить

Private Sub UserForm_Initialize()
NecessaryMiddleValue = 2.374
minPossibleValue = 0
maxPossibleValue = 5

lbMin.Caption = minPossibleValue
lbMax.Caption = maxPossibleValue
lbMid.Caption = NecessaryMiddleValue
End Sub

Private Sub CommandButton1_Click()
Dim Data(999) As Integer            'Массив с данными
Dim DataCount As Integer           'Количество данных в Data
Dim i, j As Integer                      'Счетчики
Dim Average As Long                  'Необходимое среднее умноженное на количество точек и округленное до ближайшего целого

Dim Point1 As Integer
Dim Point2 As Integer

'Общее количество точек
DataCount = UBound(Data) + 1

'Умножаю необходимое среднее арифметическое на количество точек и округляю до ближайшего целого
Average = Int(NecessaryMiddleValue * DataCount)

'Раскидываю полученное значение по всем точкам, просто по порядку
For i = 1 To Average
If i Mod (UBound(Data) + 1) = 0 Then
j = 0
j = j + 1
Else
j = j + 1
End If
Data(j - 1) = Data(j - 1) + 1
Next i

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

For i = 0 To 100000

Point1 = 0
Point2 = 0

Randomize
Do While Point1 = Point2
Point1 = Int((UBound(Data)) * Rnd) + 1
Point2 = Int((UBound(Data)) * Rnd) + 1
Loop

If Data(Point1) > minPossibleValue And Data(Point2) < maxPossibleValue Then
Data(Point1) = Data(Point1) - 1
Data(Point2) = Data(Point2) + 1
ElseIf Data(Point1) < minPossibleValue And Data(Point2) > maxPossibleValue Then
Data(Point1) = Data(Point1) + 1
Data(Point2) = Data(Point2) - 1
End If

Next

For i = 0 To UBound(Data)
Application.Worksheets("Лист1").Cells(i + 1, 1).Value = Data(i)
Next

End Sub

В результате для данных: общее количество точек 1000, минимальное значение 0, максимальное 5, необходимое среднее 2.374, я получаю это среднее и такое распределение:
Изображение

Также, сделал свой способ. Весь массив заполняется случайными целыми числами в требуемом диапазоне, и считается среднее. Если среднее больше необходимого, из случайного элемента вычитается единица, если меньше - единица прибавляется
Код: Выделить всё
Private Sub CommandButton2_Click()
Dim Data(999) As Integer
Dim ValueForFilling As Integer
Dim CurrentMiddleValue As Double
Dim SumAllValues As Long
Dim DataNumberForChange As Integer
Dim count As Long
Dim m As Integer
Dim Accuracy As Integer

count = 0
Accuracy = 4

    For m = 0 To UBound(Data)
    Randomize
    Data(m) = Int((maxPossibleValue - minPossibleValue + 1) * Rnd + minPossibleValue)
    Next m

    Do While Round(CurrentMiddleValue, Accuracy) <> Round(NecessaryMiddleValue, Accuracy)
   
    SumAllValues = 0
    For m = 0 To UBound(Data)
    SumAllValues = SumAllValues + Data(m)
    Next m
   
    CurrentMiddleValue = SumAllValues / (UBound(Data) + 1)
   
    Randomize
    DataNumberForChange = Int((UBound(Data) + 1) * Rnd)
       
    If CurrentMiddleValue > NecessaryMiddleValue And Data(DataNumberForChange) <> minPossibleValue Then
    Data(DataNumberForChange) = Data(DataNumberForChange) - 1
    End If
   
    If CurrentMiddleValue < NecessaryMiddleValue And Data(DataNumberForChange) <> maxPossibleValue Then
    Data(DataNumberForChange) = Data(DataNumberForChange) + 1
    End If
   
    count = count + 1
    If count = 100000 Then
    'MsgBox ("Достигнута максимальная точность" & " " & Round(CurrentMiddleValue, 4))
    Exit Do
    End If
       
    Loop
   
    For m = 0 To UBound(Data)
    Application.Worksheets("Лист1").Cells(m + 1, 11).Value = Data(m)
    Next
    lbMiddle.Caption = "Получено среднее значение  " & Round(CurrentMiddleValue, 4) & " за " & count & " приближений"
End Sub

При таких же требованиях получаю такое распределение:
Изображение
Мне оно нравиться больше, т.к. более похоже на данные, получаемые в ходе замеров, только иногда почему-то среднее, получаемое в процедуре, отличается от среднего, вычисленного Exel-ем по тем же данным. Возможно это как то связано с округлением.
У меня два вопроса:
1. Нормально ли использовать такое решение ? Оно правильное ?
2. Где более подробно можно почитать про алгоритм Брезенхема ?

Большое спасибо.

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 19.12.2012 (Ср) 20:43

Код не читал. Что у тебя на графике?

ZozBale
Новичок
Новичок
Аватара пользователя
 
Сообщения: 46
Зарегистрирован: 17.02.2012 (Пт) 8:37

Re: Получить из целых чисел заданное среднее

Сообщение ZozBale » 26.02.2015 (Чт) 19:16

Классическая задача на генетический алгоритм. Я в свое время очень похожую задачу решал, только там были не числа, а символы, т.е. в результате должно было получиться "Hello, World!"

Если все еще надо, могу накалякать за 15-20 минут на Пайтоне.

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2753
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 26.02.2015 (Чт) 23:21

Зачем генетический алгоритм там, где можно посчитать точно??

ZozBale
Новичок
Новичок
Аватара пользователя
 
Сообщения: 46
Зарегистрирован: 17.02.2012 (Пт) 8:37

Re: Получить из целых чисел заданное среднее

Сообщение ZozBale » 28.02.2015 (Сб) 3:58

Чтобы сделать решение хоть чуточку интересным, а то совсем тупизна какая-то. :P

Debugger
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1667
Зарегистрирован: 17.06.2006 (Сб) 15:11

Re: Получить из целых чисел заданное среднее

Сообщение Debugger » 01.03.2015 (Вс) 16:42

Тред не читал, вброшу свой алгоритм.
Начинаем с N чисел, равных среднему.
На каждом шаге мы выбираем пару чисел и генерируем случайный отступ (например, равномерный в диапазоне (-1, 1)). К первому числу прибавляем этот отступ, от второго - отнимаем.
Если после прибавления или отнимания числа вышли за пределы, отменяем шаг. Или, как альтернатива - диапазон вычисляется так, чтобы таких ситуаций не было (среднее диапазона должно быть 0).

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

Added:
Альтернативный вариант имеет склонность "прилеплять" числа к краям.

iGrok
Артефакт VBStreets
Артефакт VBStreets
 
Сообщения: 4272
Зарегистрирован: 10.05.2007 (Чт) 16:11
Откуда: Сетевое сознание

Re: Получить из целых чисел заданное среднее

Сообщение iGrok » 01.03.2015 (Вс) 18:44

Debugger писал(а):Тред не читал

А зря.
label:
cli
jmp label

ZozBale
Новичок
Новичок
Аватара пользователя
 
Сообщения: 46
Зарегистрирован: 17.02.2012 (Пт) 8:37

Re: Получить из целых чисел заданное среднее

Сообщение ZozBale » 15.03.2015 (Вс) 15:21

Мне сегодня как-то было совсем скучно, так что я наконец-то решил эту задачу через ГА. В принципе, неплохая задача, интересная, ведь надо обеспечить не только вычисление фитнесс-функции, но и как можно большее разнообразие генов. Жаль, входные данные подкачали - ответ находится уже в первой популяции. Делал по статье из Википедии - https://clck.ru/9ShT6

Код: Выделить всё
using System;
using System.Text;

namespace GeneticDiversity
{
    public static class GA
    {
        private static readonly Random RND;

        static GA()
        {
            RND = new Random();
        }

        public static double Fitness(int[] genes)
        {
            int sum = 0;
            for (int i = 0; i < genes.Length; i++)
            {
                sum += genes[i];
            }
            return Math.Abs((double)sum / (double)genes.Length - 5.12);
        }

        public static int Diversity(int[] genes)
        {
            int d = 0;
            int i;
            for (i = 0; i < genes.Length; i++)
            {
                d |= 1 << genes[i];
            }
            for (i = 0; d != 0; i += d & 1)
            {
                d >>= 1;
            }
            return i;
        }

        public static int[] RandomGenes()
        {
            int[] genes = new int[10];
            for (int i = 0; i < genes.Length; i++)
            {
                genes[i] = RND.Next(3, 9);
            }
            return genes;
        }

        public static int[] SpawnGenes(int[] fatherGenes)
        {
            int[] childGenes = new int[fatherGenes.Length];
            for (int i = 0; i < childGenes.Length; i++)
            {
                childGenes[i] = fatherGenes[i] + RND.Next(-1, 2);
                if (childGenes[i] < 3)
                {
                    childGenes[i] = 3;
                }
                else if (childGenes[i] > 8)
                {
                    childGenes[i] = 8;
                }
            }
            return childGenes;
        }
    }

    class Genome : IComparable<Genome>
    {
        private int[] GENES;
        private double FITNESS;
        private int DIVERSITY;

        public Genome(int[] genes)
        {
            GENES = genes;
            FITNESS = Double.NaN;
            DIVERSITY = 0;
        }

        public double Fitness
        {
            get
            {
                if (Double.IsNaN(FITNESS))
                {
                    FITNESS = GA.Fitness(GENES);
                }
                return FITNESS;
            }
        }

        public int Diversity
        {
            get
            {
                if (DIVERSITY == 0)
                {
                    DIVERSITY = GA.Diversity(GENES);
                }
                return DIVERSITY;
            }
        }

        public Genome Spawn()
        {
            return new Genome(GA.SpawnGenes(GENES));
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < GENES.Length; i++)
            {
                sb.Append(GENES[i]).Append(' ');
            }
            sb.Length -= 1;
            return sb.ToString();
        }

        public int CompareTo(Genome other)
        {
            if (this.Fitness == other.Fitness)
            {
                return other.Diversity - this.Diversity;
            }
            else
            {
                return this.Fitness < other.Fitness ? -1 : 1;
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Genome[] population = new Genome[20];
            int i;
            for (i = 0; i < population.Length; i++)
            {
                population[i] = new Genome(GA.RandomGenes());
            }
            do
            {
                Array.Sort(population);
                Console.WriteLine(
                    "Best genome = {0}, fitness = {1}, diversity = {2}",
                    population[0], population[0].Fitness, population[0].Diversity);
                for (i = 0; i < population.Length / 2; i++)
                {
                    population[population.Length / 2 + i] = population[i].Spawn();
                }
            }
            while (Console.ReadKey().Key != ConsoleKey.Escape);
            Console.WriteLine();
            for (i = 0; i < population.Length; i++)
            {
                Console.WriteLine(
                    "Genome[{0}] = {1}, fitness = {2}",
                    i, population[i], population[i].Fitness);
            }
        }
    }
}

alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

Re: Получить из целых чисел заданное среднее

Сообщение alibek » 15.03.2015 (Вс) 20:53

Зачем тут ГА, из любви к искусству?
Брезенхейм оптимальный и точный алгоритм.
Можно его чуть модернизировать, внося рандомные отклонения в вычисленные дельты.
Lasciate ogni speranza, voi ch'entrate.

ZozBale
Новичок
Новичок
Аватара пользователя
 
Сообщения: 46
Зарегистрирован: 17.02.2012 (Пт) 8:37

Re: Получить из целых чисел заданное среднее

Сообщение ZozBale » 16.03.2015 (Пн) 9:07

alibek писал(а):Зачем тут ГА, из любви к искусству?


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

Брезенхейм оптимальный и точный алгоритм.


И как его здесь использовать? Вы в курсе, что числа должны быть как можно более разнообразными, а не выстраиваться в нечто вроде прямой линии?

alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

Re: Получить из целых чисел заданное среднее

Сообщение alibek » 16.03.2015 (Пн) 9:37

И что тут сложного?
Lasciate ogni speranza, voi ch'entrate.

ZozBale
Новичок
Новичок
Аватара пользователя
 
Сообщения: 46
Зарегистрирован: 17.02.2012 (Пт) 8:37

Re: Получить из целых чисел заданное среднее

Сообщение ZozBale » 16.03.2015 (Пн) 19:53

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

oskolok_vatbI
Продвинутый пользователь
Продвинутый пользователь
Аватара пользователя
 
Сообщения: 112
Зарегистрирован: 07.07.2007 (Сб) 16:13
Откуда: г. Казань

Re: Получить из целых чисел заданное среднее

Сообщение oskolok_vatbI » 17.03.2015 (Вт) 13:43

alibek писал(а):И что тут сложного?

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

Если не трудно, можешь расписать ? Я не прошу код, мне на словах даже лучше.

ZozBale
Новичок
Новичок
Аватара пользователя
 
Сообщения: 46
Зарегистрирован: 17.02.2012 (Пт) 8:37

Re: Получить из целых чисел заданное среднее

Сообщение ZozBale » 18.03.2015 (Ср) 9:45

Я дал ссылку на Википедию, там есть и объяснения, и код (длиной около десятка строк). На словах объяснять лень... Может, будет настроение - объясню. Или если ты мне чем-нибудь поможешь.

Например, мне нужен совет по такой же задаче - viewtopic.php?f=57&t=40725

alibek
Большой Человек
Большой Человек
 
Сообщения: 14205
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

Re: Получить из целых чисел заданное среднее

Сообщение alibek » 18.03.2015 (Ср) 10:10

Есть нужное среднее число, A.
Нужно сгенерировать N чисел, среднее арифметическое которых будет равно (или максимально приближено) к A.
Берешь вспомогательное число A0, на первой итерации A0=A.
Генерируешь рандомное число в диапазоне -X...+X. Складываешь его с A0, получаешь первое число Т1.
Пересчитываешь A0=2*A-T1.
Повторяешь генерацию следующих чисел N раз.

Поскольку в задаче у тебя нужно использовать целые числа, значит результаты нужно округлять.
При округлении будет копиться погрешность.
Чтобы она была минимальной, нужно для округления использовать алгоритм, похожий на Брезенхейма — суммировать разницу между вычисленным и округленным значением и когда она превышает по модулю 1, прибавлять ее к округленной величине.
Lasciate ogni speranza, voi ch'entrate.

oskolok_vatbI
Продвинутый пользователь
Продвинутый пользователь
Аватара пользователя
 
Сообщения: 112
Зарегистрирован: 07.07.2007 (Сб) 16:13
Откуда: г. Казань

Re: Получить из целых чисел заданное среднее

Сообщение oskolok_vatbI » 18.03.2015 (Ср) 13:09

alibek,
Большое спасибо, попробую реализовать.

ZozBale писал(а):На словах объяснять лень... Может, будет настроение - объясню. Или если ты мне чем-нибудь поможешь.

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

Александр Дмитриев
Бывалый
Бывалый
Аватара пользователя
 
Сообщения: 296
Зарегистрирован: 05.01.2005 (Ср) 3:39
Откуда: Санкт-Петербург    Куда: /dev/null

Re: Получить из целых чисел заданное среднее

Сообщение Александр Дмитриев » 21.08.2015 (Пт) 2:26

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

Спасибо за интересную задачу! Предложу свой подход к её решению.

Пусть Изображение — количество точек, которые нужно сгенерировать (почему Изображение, станет ясно потом). Изображение — диапазон, в котором должны находиться генерируемые точки. Изображение — рациональные числа, границы допустимого диапазона среднего значения. Если точность не ниже второго знака, то Изображение.

Задача имеет решение тогда и только тогда, когда существует целое Изображение, такое что Изображение. Инструкция языка Си для проверки этого условия: (p1 * q / q1 != p2 * q / q2). В том числе задача имеет решение тогда, когда Изображение. В случае точности в несколько знаков после запятой неравенство будет выглядеть так: Изображение, а инструкция так: (p3 * q / q3 != (p3 + 1) * q / q3), а достаточное условие так: Изображение.

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

Решение задачи состоит в том, чтобы выбрать число p из диапазона возможных значений от p1 * q / q1 + 1 до p2 * q / q2 (это будет целевая сумма всех точек) и случайным образом разбить эту сумму на числа из допустимого диапазона. Изображение можно выбрать как первый элемент из числа подходящих (когда не имеет значения где среднее значение окажется внутри допустимого диапазона, в таком случае оно всегда будет в самом начале диапазона), как ближайший к требуемому среднему элемент, как случайный элемент из диапазона (выбираем распределение (например, равномерное или нормальное), подбираем вероятности элементов так, чтобы они наиболее близко походили к распределению (при этом нужно будет решить задачу математической оптимизации, в случае равномерного распределения — задачу линейного программирования) и генерировать в соответствии с этими вероятностями случайный элемент).

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

Для этого нужно подсчитать и перечислить все промежуточные состояния контейнера при переваливании его с одного бока на другой, потом, начиная с первого состояния, двигаться случайным образом по графу переходов между последовательными состояниями при переваливании с вероятностями переходов пропорциональными количеству вариантов, которые ожидаются после перехода. Это позволит сгенерировать случайный вариант из всех возможных с вероятностью (1 / количество всех возможных вариантов). Для подсчёта количества вариантов можно попробовать найти для него рекурсивное выражение через количество вариантов в контейнере меньшего размера: Изображение, но у меня не получается.

По-моему, алгоритмы Хакера, Debugger'а и alibek'a будут прилеплять точки к краям. В середине их будет разбрасывать больше к краям, а ближе к краям они будут двигаться медленней, что в итоге будет приводить к в среднем большей концентрации точек у краёв, но нужно проверять.

Кроме того, реализация алгоритма Хакера от oskolok_vatbI тоже прилепляет точки к краям (это хорошо видно на графике), но по другой причине: по причине ошибки в программе: ветка кода ElseIf Data(Point1) < minPossibleValue And Data(Point2) > maxPossibleValue Then никогда не выполняется, а в случае, когда одна из точек находится на границе, вообще ни одно условие не срабатывает и точки остаются на месте. В результате, точки могут войти на границу, но не могут выйти, и они там массово скапливаются. Вообще, реализация плохая, да и у Хакера идея не совсем додуманная. Поэтому и результаты некрасивые получились. Вот так будет правильно:

Код: Выделить всё
If Data(Point1) > minPossibleValue And Data(Point2) < maxPossibleValue And Data(Point1) < maxPossibleValue And Data(Point2) > minPossibleValue Then
If Int(2 * Rnd) = 0 Then
Data(Point1) = Data(Point1) - 1
Data(Point2) = Data(Point2) + 1
Else
Data(Point1) = Data(Point1) + 1
Data(Point2) = Data(Point2) - 1
End If
ElseIf Data(Point1) > minPossibleValue And Data(Point2) < maxPossibleValue Then
Data(Point1) = Data(Point1) - 1
Data(Point2) = Data(Point2) + 1
ElseIf Data(Point1) < maxPossibleValue And Data(Point2) > minPossibleValue Then
Data(Point1) = Data(Point1) + 1
Data(Point2) = Data(Point2) - 1
End If

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

Код: Выделить всё
For i = 0 To UBound(Data) - (Average Mod (UBound(Data) + 1))
Data(j) = (Average - (Average Mod (UBound(Data) + 1))) / (Average Mod (UBound(Data) + 1))
Next i
For i = UBound(Data) - (Average Mod (UBound(Data) + 1)) + 1 To UBound(Data)
Data(j) = ((Average - (Average Mod (UBound(Data) + 1))) / (Average Mod (UBound(Data) + 1))) + 1
Next i

В итоге в начальном раскладе получается небольшая пространственная неоднородность (слева точек немножко больше, чем справа, засчёт выложенного слева неполного ряда). С течением итераций эта неоднородность выравнивается, но при небольшом количестве итераций может быть заметна незначительная бегущая средняя. Чтобы её не было, ты должен использовать алгоритм Брезенхэма, про который говорил Хакер. При выкладывании последнего ряда ты должен выложить его не сплошной полосой, а распределив ящики приблизительно равномерно по ряду. То есть если нужно выложить половину ряда, то вместо того чтобы заполнить правую половину ряда, а оставшуюся половину оставить пустой, ты должен сначала положить один ящик, а затем одно место оставить пустым, потом снова положить один ящик, потом снова оставить место пустым. То есть сделать начальный расклад в виде зубчатки. Если последний ряд должен содержать три ящика, то ящики нужно положить в начале, в середине и в конце, оставшееся место оставить пустым, если последний ряд должен содержать на три ящика меньше, чем ширина контейнера, то нужно его полностью выложить ящиками, а три места, в начале, в середине и в конце, оставить пустыми и т. д. Это и будет реализацией того самого алгоритма, похожего на алгоритм Брезенхэма, про который говорил Хакер. В алгоритме Брезенхэма строится прямая линия из одного угла прямоугольной таблицы шириной Изображение и высотой Изображение в противоположный. Участки прямой при этом имеют только две возможных длины: результат целочисленного деления Изображение на Изображение и длина, на единицу большая этого значения. Точно так же как и у тебя: части точек выставляется значение на единицу меньше требуемого среднего, а для части — на единицу больше требуемого. В алгоритме Брезенхэма ширина таблицы приблизительно равномерно распределяется между строками таблицы, образуя Изображение участков линий, а у тебя целевая сумма приблизительно равномерно распределяется между Изображение точками. Тебе нужно реализовать определение значения точек аналогично тому, как в алгоритме Брезенхэма идёт определение ширины горизонтальных участков линий при рисовании прямой линии в таблице Изображение на Изображение. Сам алгоритм Брезенхэма описывать не буду, извини, это можно найти в Интернете без проблем, в том числе и на этом форуме.

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

Попробуй реализовать алгоритм Хакера, и построй графики распределения точек по возможным значениям (с какой частотой какие значения встречаются). Образуется ли там увеличение концентрации точек к краям диапазона?

А лучший алгоритм из всех здесь предложенных, я думаю, это твой алгоритм. Алгоритм Qwertiy является тем же самым, что и твой алгоритм, но случайность вносится в конце, а не вначале. Берётся случайный равномерно распределённый набор точек и затем по единичке уменьшаются случайные точки и сумма набора уменьшается к нужной сумме Изображение (см. выше) и среднее арифметическое к нужному значению. Постоянное движение к цели, которое всегда гарантированно даст подходящий результат. И со случайностью, и с распределением всё весьма неплохо. Только двигаться нужно к цели смелее. По одной единичке отнимать — это как девушке лайки ставить ВКонтакте. Нужно сразу приглашать девушку на свидание. То есть уменьшать случайную точку на случайное число k, которое генерируется случайным в диапазоне от 0 до значения уменьшаемой точки, как в алгоритме Хакера. Это будет то же самое, но цель будет достигнута быстрее. А ещё лучше — генетический алгоритм и генерировать популяцию. Это ещё эффективнее. Это то же самое, что и твой метод, только движение к цели будет идти сразу в несколько потоков. Некоторые сперматозоиды будут двигаться медленно и не туда, и они отомрут через некоторое время, а некоторые будут двигаться быстро и к цели. Один из числа последних (такой, который сразу на k шагов вперёд мутирует), в конце концов, добъётся внимания требуемого среднего значения, то есть добъется определённого в условии задачи уровня близости с ней.

oskolok_vatbI писал(а):alibek,
Большое спасибо, попробую реализовать.

Ну как дела, реализовал?
Википедия — это наилучший источник информации по теме «Википедия».


Вернуться в Алгоритмы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 7

    TopList