Форум программистов, компьютерный форум, киберфорум
Наши страницы
VBA
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.87/15: Рейтинг темы: голосов - 15, средняя оценка - 4.87
Jozin
0 / 0 / 0
Регистрация: 23.07.2013
Сообщений: 9
1

Задача с простыми числами

06.09.2016, 21:22. Просмотров 2764. Ответов 9
Метки нет (Все метки)

Добрый вечер!
Решил поступить в школу программистов Head Hunter, а там при заполнении анкеты дано 5 задач. Не могу эту решить. В универе проходил VBA, поэтому обратился сюда.

Определим функцию P(n,k) следующим образом: P(n,k) = 1, если n может быть представлено в виде суммы k простых чисел (простые числа в записи могут повторяться, 1 не является простым числом) и P(n,k) = 0 в обратном случае.
К примеру, P(10,2) = 1, т.к. 10 может быть представлено в виде суммы 3 + 7 или 5 + 5, а P(11,2) = 0, так как никакие два простых числа не могут дать в сумме 11.
Определим функцию S(n) как сумму значений функции P(i,k) для всех i и k, таких что 1≤i≤n, 1≤k≤n. Таким образом, S(2) = P(1,1) + P(2,1) + P(1,2) + P(2,2) = 1, S(10) = 20, S(1000) = 248838.

Найдите S(10992).

Перебирать я так понимаю не имеет смысла - слишком громоздко. Решил методом исключения действовать. Результат не сходится уже для 1000. Что-то упустил.
Правильное ли направление поиска решения или нет?
Это юзерформа.

Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Private Sub CommandButton1_Click()
 
n = TextBox1
s = 0
p = 0
 
For i = 1 To n
    For j = 1 To n
    
    If i < j * 2 Then p = 0 Else p = 1
    
    If i Mod 2 = 0 And j = 1 Then p = 0
    
    s = s + p
        
    Next j
Next i
 
TextBox1 = s
 
End Sub
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.09.2016, 21:22
Ответы с готовыми решениями:

Операции с простыми числами
Дано целое число N (&gt; 1). Если оно является простым, то есть не имеет положительных делителей,...

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

Задача с простыми числами
составить программу нахождения и печати всех простых чисел,меньших заданного числа N.Подсчитать...

Задача по функциям! Заменить непростые числа в матрице ближайшими к ним простыми" числами
Уважаемые программисты, помогите решить задачу &quot;Заменить непростые числа в матрице ближайшими к ним...

Вывести на экран числа, являющиеся одновременно простыми числами и числами Фибоначчи
Помогите составить программу: С клавиатуры вводится натуральное число N(N&lt;=1 000 000 000)....

9
Burk
962 / 671 / 200
Регистрация: 11.07.2014
Сообщений: 2,377
07.09.2016, 09:47 2
Jozin, сразу уточнить бы надо, что-то я не вижу К, а в задании P(n,k). Если речь идет о любом числе К - это одно, а нет, то ..... Пока я вижу, что алгоритм, написанный вами, слишком прост для такой задачи, ведь перебирая числа нужно и их проверять на ПРОСТОТУ. Может потребоваться рекурсивное обращение к функции поиска или при переборе чисел запоминать предыдущие простые. Уточните

Добавлено через 9 минут
P.S. А ещё вот что, по теории простых чисел число 5 является простым т.е. делится только на само себя и единицу. , a у вас 5=3+2
Может ваша задача переопределяет простые числа как ряд от 2 до 9?????
0
m-ch
5560 / 843 / 281
Регистрация: 25.02.2011
Сообщений: 1,196
Записей в блоге: 1
07.09.2016, 14:03 3
у меня перебором получилось:
S(10992) = 30192198

Добавлено через 1 час 38 минут
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
Sub www()
    Dim i As Long, j As Long, k As Long, n As Long, l As Long, m As Long
    Dim b(1 To 1334) As Long, s As Double, t As Single
    n = 10992 '1000
    
    t = Timer
    'заполняем массив b() простыми числами
    b(1) = 2 'первое простое число - 2
    b(2) = 3
    k = 2 'счетчик простых чисел
    For i = 5 To n Step 2 'вычисляем все простые числа до n, перебираем нечетные числа
    For j = 2 To k 'проверку деления на 2 исключаем
        If i Mod b(j) = 0 Then Exit For
        If b(j) * b(j) > i Then
            k = k + 1 'увеличиваем счетчик простых чисел
            b(k) = i 'запоминаем простое число
            Exit For
        End If
    Next j, i
    'вычисляем количество вариантов перебором
    ReDim p(n, n) As Byte, c(n) As Long
    p(0, 0) = 1
    For l = 1 To n
        For i = 1 To k
            m = c(l - 1) + b(i)
            If m > n Then m = n
            For j = b(i) + (l - 1) * 2 To m
                If p(j - b(i), l - 1) Then
                    p(j, l) = 1
                    If j > c(l) Then c(l) = j
                End If
        Next j, i
        If c(l) = 0 Then Exit For
    Next l
    For i = 1 To n 'вычисляем s(n)
        For j = 2 * i To c(i)
            s = s + p(j, i)
    Next j, i
    Debug.Print s, Timer - t
End Sub
s(1000) - считается менее 1 секунды
s(10992) - 12 минут

Добавлено через 8 минут
upd
0
Jozin
0 / 0 / 0
Регистрация: 23.07.2013
Сообщений: 9
07.09.2016, 14:37  [ТС] 4
Спасибо!
0
07.09.2016, 14:37
m-ch
5560 / 843 / 281
Регистрация: 25.02.2011
Сообщений: 1,196
Записей в блоге: 1
08.09.2016, 08:34 5
Лучший ответ Сообщение было отмечено Sasha_Smirnov как решение

Решение

Немного сократил лишние расчеты, считает s(10992) менее 5 минут (но все равно долго):
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
Sub www()
    Dim i As Long, j As Long, k As Long, n As Long, l As Long
    Dim b(1 To 1334) As Long, s As Long, t As Single
    n = 10992 '1000
    t = Timer
    'заполняем массив b() простыми числами
    b(1) = 2 'первое простое число - 2
    b(2) = 3
    k = 2 'счетчик простых чисел
    For i = 5 To n Step 2 'вычисляем все простые числа до n, перебираем нечетные числа
    For j = 2 To k 'проверку деления на 2 исключаем
        If i Mod b(j) = 0 Then Exit For
        If b(j) * b(j) > i Then
            k = k + 1 'увеличиваем счетчик простых чисел
            b(k) = i 'запоминаем простое число
            Exit For
        End If
    Next j, i
    'вычисляем количество вариантов перебором
    ReDim p(n, n \ 2) As Boolean
    p(0, 0) = True
    For l = 1 To n \ 2
      For i = 1 To k
        For j = b(i) + (l - 1) * 2 To n
            If Not p(j, l) Then
                If p(j - b(i), l - 1) Then
                    s = s + 1
                    p(j, l) = True
                End If
            End If
    Next j, i, l
    Debug.Print s, Timer - t
End Sub
Добавлено через 10 часов 59 минут
вот этот код считает практически моментально:
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
Sub www2()
    Dim i As Long, j As Long, k As Long, n As Long, l As Long, m As Long
    Dim b(1 To 1334) As Long, s As Long, t As Single
    n = 10992 '1000
    t = Timer
    'заполняем массив b() простыми числами
    b(1) = 2 'первое простое число - 2
    b(2) = 3
    k = 2 'счетчик простых чисел
    For i = 5 To n Step 2 'вычисляем все простые числа до n, перебираем нечетные числа
    For j = 2 To k 'проверку деления на 2 исключаем
        If i Mod b(j) = 0 Then Exit For
        If b(j) * b(j) > i Then
            k = k + 1 'увеличиваем счетчик простых чисел
            b(k) = i 'запоминаем простое число
            Exit For
        End If
    Next j, i
    'вычисляем количество вариантов перебором
    ReDim p(n, 3) As Boolean
    p(0, 0) = True
    For l = 1 To 3
        m = 0
        For i = 1 To k
            For j = b(i) + (l - 1) * 2 To n
                If Not p(j, l) Then
                    If p(j - b(i), l - 1) Then
                        s = s + 1
                        m = m + 1
                        p(j, l) = True
                    End If
                End If
    Next j, i, l
    For i = l To n \ 2
        m = m - 2
        s = s + m
    Next i
    Debug.Print s, Timer - t
End Sub
1
bot1no4ek
0 / 0 / 0
Регистрация: 08.09.2016
Сообщений: 1
08.09.2016, 15:33 6
Цитата Сообщение от m-ch Посмотреть сообщение
Немного сократил лишние расчеты, считает s(10992) менее 5 минут (но все равно долго):
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
Sub www()
    Dim i As Long, j As Long, k As Long, n As Long, l As Long
    Dim b(1 To 1334) As Long, s As Long, t As Single
    n = 10992 '1000
    t = Timer
    'заполняем массив b() простыми числами
    b(1) = 2 'первое простое число - 2
    b(2) = 3
    k = 2 'счетчик простых чисел
    For i = 5 To n Step 2 'вычисляем все простые числа до n, перебираем нечетные числа
    For j = 2 To k 'проверку деления на 2 исключаем
        If i Mod b(j) = 0 Then Exit For
        If b(j) * b(j) > i Then
            k = k + 1 'увеличиваем счетчик простых чисел
            b(k) = i 'запоминаем простое число
            Exit For
        End If
    Next j, i
    'вычисляем количество вариантов перебором
    ReDim p(n, n \ 2) As Boolean
    p(0, 0) = True
    For l = 1 To n \ 2
      For i = 1 To k
        For j = b(i) + (l - 1) * 2 To n
            If Not p(j, l) Then
                If p(j - b(i), l - 1) Then
                    s = s + 1
                    p(j, l) = True
                End If
            End If
    Next j, i, l
    Debug.Print s, Timer - t
End Sub
Добавлено через 10 часов 59 минут
вот этот код считает практически моментально:
Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
Sub www2()
    Dim i As Long, j As Long, k As Long, n As Long, l As Long, m As Long
    Dim b(1 To 1334) As Long, s As Long, t As Single
    n = 10992 '1000
    t = Timer
    'заполняем массив b() простыми числами
    b(1) = 2 'первое простое число - 2
    b(2) = 3
    k = 2 'счетчик простых чисел
    For i = 5 To n Step 2 'вычисляем все простые числа до n, перебираем нечетные числа
    For j = 2 To k 'проверку деления на 2 исключаем
        If i Mod b(j) = 0 Then Exit For
        If b(j) * b(j) > i Then
            k = k + 1 'увеличиваем счетчик простых чисел
            b(k) = i 'запоминаем простое число
            Exit For
        End If
    Next j, i
    'вычисляем количество вариантов перебором
    ReDim p(n, 3) As Boolean
    p(0, 0) = True
    For l = 1 To 3
        m = 0
        For i = 1 To k
            For j = b(i) + (l - 1) * 2 To n
                If Not p(j, l) Then
                    If p(j - b(i), l - 1) Then
                        s = s + 1
                        m = m + 1
                        p(j, l) = True
                    End If
                End If
    Next j, i, l
    For i = l To n \ 2
        m = m - 2
        s = s + m
    Next i
    Debug.Print s, Timer - t
End Sub
Добрый день,

Сам недавно разбирал эту задачу и хотелось бы спросить, можно поподробнее о логике перебора вариантов? Получить результат конечно хорошо, но никак не могу понять самого алгоритма.
0
m-ch
5560 / 843 / 281
Регистрация: 25.02.2011
Сообщений: 1,196
Записей в блоге: 1
08.09.2016, 18:51 7
Цитата Сообщение от bot1no4ek Посмотреть сообщение
но никак не могу понять самого алгоритма.
Вначале заносим все простые числа в массив b(), код с 7 по 18 строчку, надеюсь не нужно объяснять код, он достаточно подробно прокомментирован.

Далее, на примере первого кода из 5го поста:
Фактически вычисления производятся динамическим программированием.

Создаем булевый массив p(i,j) в котором будет хранится информация, можем ли мы получить число i (первое измерение массива) используя j слагаемых (второе измерение массива), true – можем, false – не можем.
Стартовая точка p(0,0) = true, т.к. используя ноль слагаемых можно получить сумму ноль
Цикл по L – количество слагаемых, считаем до n\2, т.к. минимальное простое число – 2, поэтом для получения числа n максимум потребуется n\2 слагаемых (или меньше)
Цикл по i – перебираем все простые числа в массиве b()
Цикл по j – проверяем для каждого простого числа, можем ли мы получить сумму j используя L слагаемых
Для L слагаемых можно получить сумму не менее 2*L, поэтому цикл начинаем не с нуля.
Строка 25: Если сумма p(j,L) еще не находилась, то проверяем, а была ли достигнута сумма из L-1 слагаемых и менее на величину очередного простого числа, если да, то увеличиваем счетчик s, помечаем что число j можно получить используя L слагаемых.

Проанализировав вычисления, выяснилось, что можно получить любое число не менее 2*L используя 3 и более слагаемых, поэтому для 1<=L<=3 вычисляем по указанному алгоритму, определяем количество в переменной m, далее получаем конечную величину s(n) - простой цикл (34-37 строчки, второго кода).
Вместо цикла можно было бы вычислить одной операцией используя формулу суммы арифметической прогрессии, но цикл написать значительно проще, чем отлаживать формулу (хотя формула и простая)
0
topdownofworld
0 / 0 / 0
Регистрация: 03.05.2015
Сообщений: 8
23.09.2016, 11:17 8
Вы не могли бы подсчитать для S(14340), буду крайне благодарен
0
m-ch
5560 / 843 / 281
Регистрация: 25.02.2011
Сообщений: 1,196
Записей в блоге: 1
23.09.2016, 11:48 9
у меня получилось:
S(14340) = 51390754
0
Vasysyaka
0 / 0 / 0
Регистрация: 27.09.2016
Сообщений: 1
27.09.2016, 02:18 10
Прошу прощения за наглость, на новой визуалке vba ругается по коду, не могли бы подсчитать для s(15983), заранее спасибо)
0
27.09.2016, 02:18
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.09.2016, 02:18

Найти все натуральные числа меньше N, которые одновременно являются числами Фибоначчи и простыми числами.
Дано натуральное число N. Найти все натуральные числа меньше N, которые одновременно являются...

Найти все натуральные числа меньше N, которые одновременно являются числами Фибоначчи и простыми числами
Дано натуральное число N. Найти все натуральные числа меньше N, которые одновременно являются...

Работа с простыми числами
FORTRAN 77 - FORCE Доброго времени суток! Есть задача: Можно ли представить по крайней...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.