Блог

У меня есть книга с N <10000 страниц и числом x (в диапазоне 1 <= x <= 40). Я хочу вычислить вероятность того, что при случайном открытии этой книги комбинация цифр открытых страниц книги будет равна числу.

«Уровень комбинаций» может варьироваться: от простой суммы цифр (событие стр.234 верно для x = 9) до комбинации сумм и вычитаний вплоть до пар цифр [событие стр.124 верно для x = 1, 2, 3(4-1), 4, 5(4 1), 6(2 4), 7(1 2 4), 8(12-4), 12, 14, 16(14 2), 23(24-1), 24, 25(24 1) ]

Начальное замечание заключается в том, что если вы откроете книгу, вы всегда получите страницу n и страницу n 1, поэтому вероятность должна быть рассчитана для пары (2n-1,2n), для каждого n, 1

Вот что я делаю

 static protected int sommaCifreNumero(int numero){
    int retnum=0;
    for (char c : Integer.valueOf(numero).toString().toCharArray()){
        retnum  = c - 48;
    }
    return retnum;
}

static public float calcolaProbabilitàSemplice(int da_interrogare, int ne_interroga)
{
    return (float)ne_interroga/(float)da_interrogare*100f;
}

/*
 * Questo sistema calcola le probabilità che aprendo un libro a caso, 
 * la somma delle cifre delle pagine diano il tuo numero nell'elenco del registro.
 * Se il tuo numero non può essere raggiunto, avrai sempre probabilità 0%.
 */

static public float calcolaProbabilitàLibroSemplice(int nPagine, int nRegistro)
{
    int maxNumberInterrogabile = 0;
    float retProb;
    maxNumberInterrogabile = sommaCifreNumero (nPagine);
    maxNumberInterrogabile = ((Integer.valueOf(nPagine).toString().length() == 2) amp;amp; (Integer.valueOf(nPagine).toString().toCharArray()[1] -48 -1   9*1)>maxNumberInterrogabile) ? (Integer.valueOf(nPagine).toString().toCharArray()[1] -48 -1   9*1) : maxNumberInterrogabile;
    maxNumberInterrogabile = ((Integer.valueOf(nPagine).toString().length() == 3) amp;amp; (Integer.valueOf(nPagine).toString().toCharArray()[2] -48 -1   9*2)>maxNumberInterrogabile) ? (Integer.valueOf(nPagine).toString().toCharArray()[1] -48 -1   9*2) : maxNumberInterrogabile;
    maxNumberInterrogabile = ((Integer.valueOf(nPagine).toString().length() == 4) amp;amp; (Integer.valueOf(nPagine).toString().toCharArray()[3] -48 -1   9*3)>maxNumberInterrogabile) ? (Integer.valueOf(nPagine).toString().toCharArray()[1] -48 -1   9*3) : maxNumberInterrogabile;

    if(nRegistro>maxNumberInterrogabile)
    {
        retProb = 0.f;
        return 0.f;
    }//il numero massimo raggiungibile è inferiore al numero in registro -> non puoi essere chiamato
    int favorevoli = 0;
    for(int i=1; i<=nPagine; i  )
    {
        if(sommaCifreNumero(i)==nRegistro || i==nRegistro)
            favorevoli  ;
    }

    retProb = (float) favorevoli / (float) nPagine * 100f;
    return retProb;
}

/*
 * Questo sistema è un'estensione del precedente: somma le cifre 
 * di una pagina aperta a caso, ma anche a coppie(es: p.124 può dare 12, 16, 24, 25).
 */

static public float calcolaProbabilitàLibroComplessa(int nPagine, int nRegistro)
{
    String pagstring;
    float retProb;
    int nRegLength = String.valueOf(nRegistro).length();
    int favorevoli = 0;
    int totali = 0;
    Vector<Integer> possibili;
    int number_to_add;
    int number_added;
    for(int i = 1;i<=nPagine; i  )
    {
        possibili = new Vector<Integer>();
        pagstring = Integer.valueOf(i).toString();
        for(int a=0; a nRegLength<=pagstring.length(); a  )
        {
            String numero_selezionato = pagstring.substring(a,a nRegLength);

            if (Integer.parseInt(numero_selezionato)<=31)  possibili.add(Integer.parseInt(numero_selezionato));
            //somma le parti prima
            for(int b=0; b<a; b  )
            {//b è l'indice iniziale della sottostringa che verrà sommata
                for(int c=1; c<=nRegLength; c  )
                {//c è l'indice  1 finale della sottostringa che verrà sommata
                    if(b c<=a)
                    {
                        number_to_add = Integer.parseInt(pagstring.substring(b,b c));
                        if (number_to_add!=0)
                        {
                            number_added = Integer.parseInt(numero_selezionato)   number_to_add;
                            if (number_added <31) possibili.add(number_added);
                        }
                    }
                }
            }
            //somma le parti dopo
            for(int b=a nRegLength; b<pagstring.length(); b  )
            {
                for(int c=1; c<=nRegLength; c  )
                {
                    if(b c<=pagstring.length())
                    {
                        number_to_add = Integer.parseInt(pagstring.substring(b,b c));
                        if (number_to_add!=0)
                        {
                            number_added = Integer.parseInt(numero_selezionato)   number_to_add;
                            if (number_added <31) possibili.add(number_added);
                        }
                    }
                }
            }
            totali  = possibili.size();
            for(int numero: possibili) favorevoli = numero==nRegistro ? 1:0;

        }
    }
    retProb = (float)favorevoli/(float)totali * 100f;
    return retProb;
}
  

Первый метод вычисляет сумму цифр числа, второй — вероятность того, что номер открытой страницы равен x, или сумма их цифр равна.
Третья проверка также пары цифр.

1) Я не учитываю заметку, которую я сделал раньше.

2) Я запущу это на мобильном устройстве.

3) Прямо сейчас я действительно чувствую, что результаты неверны.

Мне было интересно, подойдет ли таблица предварительно рассчитанных результатов лучше. Я знаю, что N равно <10000, поэтому я могу использовать массив [40] [10000] для хранения результатов для загрузки во время выполнения, но я не увлекаюсь манипуляциями с файлами в Java, кроме того, мне нужно будет сохранить это, скажем, для 4 разных методов вычисления вероятностиитак, сколько памяти это будет потреблять? И является ли проблемой вычислить это во время выполнения вместо этого? Есть ли лучший подход (или, может быть, уже написанный алгоритм) для этого?

Подсчитайте количество сумм, которые у вас будут с 1 <= страница # <= N, где N — количество страниц. Это намного меньше 10 000, потому что 1, 10, 100, 1000 и 10000 сопоставляются с суммой 1. Максимальное значение, которое у вас будет, равно 9999 => 36. Вы можете начать с карты, где страница # — это ключ, а сумма — значение, затем перевернуть ее и получить карту, где сумма — это ключ, а список страниц, сумма номеров которых равна ключу, — это значение.

Для 10 000 страниц все возможные суммы находятся в диапазоне от 1 до 36.

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

Вот как я бы это сделал:

 package misc;

import java.util.*;

/**
 * PageSumProbability
 *
 * @author Michael
 * @since 10/14/11
 */
public class PageSumProbability {

    private Map<Integer, Integer> pageNumberSum;
    private Map<Integer, List<Integer>> sumPageNumbers;

    public static void main(String[] args) {
        if (args.length > 1) {
            int maxPageNumber = Integer.valueOf(args[0]);            
            int randomSum = Integer.valueOf(args[1]);
            PageSumProbability psp = new PageSumProbability(maxPageNumber);
            System.out.println(psp.getPageNumberSum());
            System.out.println(psp.getSumPageNumbers());
            System.out.printf("random sum: %d probability of opening page # that equals random sum: %5.3f%%n",
                    randomSum, 100*psp.getProbabilityOfSum(randomSum));
        } else {
            System.out.print("Usage: PageProbabilitySum <# pages> <random sum>");
        }
    }

    public PageSumProbability(int maxPageNumber) {
        this.pageNumberSum = new TreeMap<Integer, Integer>();
        this.sumPageNumbers = new TreeMap<Integer, List<Integer>>();

        for (int i = 1; i <= maxPageNumber;   i) {
            int sum = this.calculateSumOfDigits(i);
            this.pageNumberSum.put(i, sum);
            List<Integer> pages = this.sumPageNumbers.get(sum);
            if (pages == null) {
                pages = new LinkedList<Integer>();
            }
            pages.add(i);
            this.sumPageNumbers.put(sum, pages);
        }
    }

    public static int calculateSumOfDigits(int pageNumber) {
        int sum = 0;
        String pageNumberAsString = String.valueOf(Math.abs(pageNumber));
        for (int i = 0; i < pageNumberAsString.length();   i) {
            StringBuilder digit = new StringBuilder();
            digit.append(pageNumberAsString.charAt(i));
            sum  = Integer.valueOf(digit.toString());
        }

        return sum;
    }

    public double getProbabilityOfSum(int randomSum) {
        if (randomSum <= 0)
            throw new IllegalArgumentException("random sum must be greater than zero");
        double probability = 0.0;
        List<Integer> pages = this.sumPageNumbers.get(randomSum);
        if (pages != null) {
            probability = (double) pages.size()/this.pageNumberSum.size();
        }

        return probability;
    }

    public Map<Integer, Integer> getPageNumberSum() {
        return Collections.unmodifiableMap(this.pageNumberSum);
    }

    public Map<Integer, List<Integer>> getSumPageNumbers() {
        return Collections.unmodifiableMap(this.sumPageNumbers);
    }
}
  

Вот как я бы это сделал.

Определите интерфейс DigitCombinationStragtegy с помощью одного метода: Set<Integer> combineDigits(int pageNumber) .

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

Напишите реализацию этой стратегии, которая просто использует набор других стратегий и объединяет все наборы, которые они возвращают.

При запросе книги и числа N инициализируйте два числа 0: hits и misses . Создайте экземпляр соответствующей стратегии. Перебирайте страницы (или пары страниц) и запрашивайте у стратегии набор чисел, которые она генерирует. для этой страницы (или этой пары страниц). Если набор содержит N, выполняется увеличение. Иначе приращение не выполняется.

Вероятность равна попаданиям / (попаданиям промахам).