Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.88/40: Рейтинг темы: голосов - 40, средняя оценка - 4.88
 Аватар для Mikstereo
98 / 36 / 18
Регистрация: 05.11.2018
Сообщений: 231

Найти количество счастливых чисел не больших заданного N

11.11.2018, 15:12. Показов 8096. Ответов 40

Студворк — интернет-сервис помощи студентам
Все знают, что счастливые числа - это те числа, которые содержат только счастливые цифры 7 и/или 4. Вам нужно найти количество счастливых чисел не больших N.
Входные данные:В единственной строке входного потока записано натуральное число N, не превышающее 1032.
Пример входного файла (input.txt):
56
Выходные данные:В единственную строку выходного потока нужно вывести одно целое число.
Пример выходного файла (output.txt):
4
Мой код:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function Lucky(n:int64):boolean;
begin
lucky:=true;
if (n=0) then exit else
  begin
    while n>0 do begin
      if (n mod 10<>4) and (n mod 10<>7) then Lucky:=false;
      n:=n div 10;
      end;
end;
end;
var n,i,k:int64; //или qword,тут разницы нет
begin
  read(n);
  k:=0;
  for I:=1 to n do
  begin
    if Lucky(i) then k:=k+1;
    end;
    write(k);
end.
Дело в том,что не работает на больших числах или зацикливается(работает слишком долго),как реализовать это для больших чисел?Слышал что-то про степени двойки,но конкретной закономерности не нашел.Помогите пожалуйста.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
11.11.2018, 15:12
Ответы с готовыми решениями:

Найти среднее арифметическое чисел, больших заданного D и стоящих на нечетных местах
Найти среднее арифметическое чисел, больших заданного D и стоящих на нечетных местах, и определить количество чисел, небольших заданного F....

Найти сумму всех элементов массива вещественных чисел, больших заданного числа
Условие: Найти сумму всех элементов массива вещественных чисел, больших заданного числа. Размерность массива – 20. Заполнение массива...

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

40
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7816 / 4635 / 2837
Регистрация: 22.11.2013
Сообщений: 13,158
Записей в блоге: 1
11.11.2018, 15:34
Воспользуйтесь для подсчета комбинаторикой, вам же не нужно находить сами числа, нужно только их количество.

Добавлено через 9 минут
Если же перебирать сами числа, то QWord даст вам только 2^64, что чуть меньше, чем 2*10^20.
В любом случае, никаких делений и проверок на 4 и 7 не нужно, последовательность довольно проста:
4, 7, 44, 47, 74, 77, 444, 447, 474, 477, ...
Про степени двойки: у вас всего 2 цифры, примем 4 за 0, 7 за 1, на 32 битах получите все возможные числа.

Осталось только из граничного числа выделить максимальное подходящее (из 4 и 7) -- оно (из 0 и 1) и будет искомым количеством, да?

Добавлено через 3 минуты
На самом деле не совсем, но близко, нужно учесть числа с ведущими нулями, вида 44 (00), 47 (01), 444 (000), 447 (001).
1
 Аватар для Mikstereo
98 / 36 / 18
Регистрация: 05.11.2018
Сообщений: 231
11.11.2018, 16:16  [ТС]
Цитата Сообщение от bormant Посмотреть сообщение
будет искомым количеством
А как это сделать в паскале?Есть ли какая-то формула как вывести количество из двоичного представления счастливых чисел?А то простой перебор всех возможных счастливых чисел и сравнение их с текущим это не очень быстрый алгоритм.

Добавлено через 3 минуты
Цитата Сообщение от bormant Посмотреть сообщение
максимальное подходящее
Найти наибольшее счастливое число до заданного n,хорошо,это не слишком сложно.

Добавлено через 1 минуту
Цитата Сообщение от Mikstereo Посмотреть сообщение
наибольшее счастливое число
Но как это поможет уменьшить число итераций ?
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7816 / 4635 / 2837
Регистрация: 22.11.2013
Сообщений: 13,158
Записей в блоге: 1
11.11.2018, 16:35
56, максимальное подходящее: 44, в двоичной системе 100 (именно так мы избавимся от ведущих нулей), 1002=410.
Осталось запрограммировать эту тривиальщину.

Добавлено через 1 минуту
Mikstereo,
взялись решать олимпиаду, включайте голову, работайте ей, ищите варианты решений, проверяйте их на практике.
Иначе ничего не получится. Совсем.

Добавлено через 4 минуты
либо 56, максимальное подходящее: 47, в двоичной 101, 1012-1=1002=410.

Я не знаю, как именно это выглядит, проверяйте гипотезы, разбирайтесь... Возможно есть еще нюансы, которые остались за кадром. Работайте головой...
1
 Аватар для Mikstereo
98 / 36 / 18
Регистрация: 05.11.2018
Сообщений: 231
11.11.2018, 16:42  [ТС]
Цитата Сообщение от bormant Посмотреть сообщение
в двоичной системе 100
44 в двоичной 101100

Добавлено через 37 секунд
Цитата Сообщение от bormant Посмотреть сообщение
в двоичной системе 100
Если обьясните как из 101100 вы получили 100 я проверю верно ли это для больших чисел
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7816 / 4635 / 2837
Регистрация: 22.11.2013
Сообщений: 13,158
Записей в блоге: 1
11.11.2018, 17:02
Уже объяснил, см. сообщение #2. Есть смысл объяснять больше одного раза или сами вернетесь и перечитаете? Или, перефразируя одного сценического героя Райкина: здесь читаем, здесь -- не читаем, здесь рыбу заворачивали?
Цитата Сообщение от bormant Посмотреть сообщение
Про степени двойки: у вас всего 2 цифры, примем 4 за 0, 7 за 1, на 32 битах получите все возможные числа.
... нужно учесть числа с ведущими нулями, вида 44 (00), 47 (01), 444 (000), 447 (001).
Добавлено через 3 минуты
"все возможные" -- все возможные искомые счастливые числа. Если придумаете, что делать с мнимой 1.

Добавлено через 9 минут
Одна из "придумок" есть в #4: просто дополнять реальной единицей и вычитать 1 -- непредставимое в такой системе число 4 (02), поскольку с явной 1 это 102.
1
 Аватар для Mikstereo
98 / 36 / 18
Регистрация: 05.11.2018
Сообщений: 231
11.11.2018, 18:08  [ТС]
Цитата Сообщение от bormant Посмотреть сообщение
явной 1 это 102.
У меня такая идея:56=111000 в двоичной, по вашему способу это 777444(4=0,7=1),получить все возможные комбинации чисел из цифр этого числа и проверить,какие из них меньше либо равны заданному числу(каждая такая комбинации увеличивает количество таких чисел на 1).Но как быть с https://www.cyberforum.ru/cgi-bin/latex.cgi?{10}^{32} ? В целочисленные типы не влазит.

Добавлено через 2 минуты
Цитата Сообщение от Mikstereo Посмотреть сообщение
это 777444
Т.е.,цифры 7,7,7,4,4,4.Из них можно составить такие комбинации:7,4,74,744,7444,77,777,но нам нужны и эти числа наоборот(еще же есть 47 для исходного числа 56).Как можно наиболее оптимизированно получить все комбинации?
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7816 / 4635 / 2837
Регистрация: 22.11.2013
Сообщений: 13,158
Записей в блоге: 1
11.11.2018, 19:46
Вы все немного перепутали. Повторю:
1) для исходного числа 56 нужно найти ближайшее меньшее счастливое, это 47,
2) найденное число представить в двоичной системе исходя из только двух возможных цифр (4 и 7 как 0 и 1), на этом этапе это возможно, цифр может быть до 32 шт, 32 бит должно хватить, с оговоркой про мнимую старшую единицу,
3) по полученному представлению получить искомое количество чисел.
1
 Аватар для Mikstereo
98 / 36 / 18
Регистрация: 05.11.2018
Сообщений: 231
11.11.2018, 21:03  [ТС]
Цитата Сообщение от bormant Посмотреть сообщение
32 бит должно хватить
Как такое возможно? А если число огромное? Например 4477447474747774 ?
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7816 / 4635 / 2837
Регистрация: 22.11.2013
Сообщений: 13,158
Записей в блоге: 1
11.11.2018, 21:08
Code
1
2
 4477447474747774
10011001010101110(2) = 78510(10)
78509 счастливых чисел, не превышающих 4477447474747774.
1
 Аватар для Mikstereo
98 / 36 / 18
Регистрация: 05.11.2018
Сообщений: 231
11.11.2018, 21:25  [ТС]
Цитата Сообщение от bormant Посмотреть сообщение
10011001010101110
а если будет 32-х значное счастливое число?
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7816 / 4635 / 2837
Регистрация: 22.11.2013
Сообщений: 13,158
Записей в блоге: 1
11.11.2018, 21:49
... то придется вспомнить про мнимую 1 и куда ее пристроить. При наличии 64-битных типов данных можно вообще этим не заморачиваться:
Code
1
2
  77777777 77777777 77777777 77777777
1 11111111 11111111 11111111 11111111 (2) = 8 589 934 591
8 589 934 590 счастливых чисел.

Добавлено через 8 минут
Code
1
2
3
4
5
6
7
   4    10(2)-1 = 2-1 = 1
   7    11(2)-1 = 3-1 = 2
  44   100(2)-1 = 4-1 = 3
  47   101(2)-1 = 5-1 = 4
  74   110(2)-1 = 6-1 = 5
  77   111(2)-1 = 7-1 = 6
... далее по индукции ...
Мы об этом с сообщения #2 говорим, пошли уже по третьему кругу...
1
 Аватар для Mikstereo
98 / 36 / 18
Регистрация: 05.11.2018
Сообщений: 231
12.11.2018, 10:55  [ТС]
Цитата Сообщение от bormant Посмотреть сообщение
Вы все немного перепутали. Повторю:
1) Найдем это число в промежутке n..n div 10(downto)
2)
Pascal
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
while b<>0 do
    begin
      c:=b mod 10;
      if (c=1) then c:=7 else
      if (c=0) then c:=4;
      k:=k*10+c;
      //if (b mod 10=7) then c:=c*10+7 else
     // if (b mod 10=4) then c:=c*10+4;
      b:=b div 10;
      end;
      while k<>0 do
    begin
      g:=g*10+k mod 10;
      //if (c=1) then c:=7 else
      //if (c=0) then c:=4;
      r:=r*10+g;
      //if (b mod 10=7) then c:=c*10+7 else
     // if (b mod 10=4) then c:=c*10+4;
      k:=k div 10;
      end;
      переменная g будет со
где b- результат перевода из 10 в двоичную
3)
const digit:string[2]='01'; //цифры в СС 2
var s2:string;
    n,i:integer;
begin
writeln('Введите число в СС 2');
readln(s2);
while s2[1]='0' do
delete(s2,1,1);//удалим ведущие ноли
n:=0; //получим число в СС 10
for i:=1 to length(s2) do
n:=n*2+pos(s2[i],digit)-1;
write('n=',n)
end.
Полная программа(в результате выдает двоичную запись числа,если вначале введено максимальное)
Pascal
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
  var s2:string;
const digit:string[2]='01';
function r1(s2:string):longint;
var i,n:integer;
begin
//const digit:string[2]='01'; //цифры в СС 2
//var s2:string
//n,i:integer;
//begin
//writeln('Введите число в СС 2');
//readln(s2);
while s2[1]='0' do
delete(s2,1,1);//удалим ведущие ноли
n:=0; //получим число в СС 10
for i:=1 to length(s2) do
n:=n*2+pos(s2[i],digit)-1;
//write('n=',n)
end;
function dec2bin(x:integer):string;
var s:string;
begin
s:='';
  while x>0 do
  begin
     s:=chr(ord('0')+x mod 2)+s;
     x:=x div 2;
  end;
dec2bin:=s;
end;
var a,b,c,d,k,g,r,m,P,U:uint64;
begin
  read(a);
  b:=strtoint(Dec2Bin(a));
  d:=b;
  c:=0;
  k:=0;
  g:=0;
  r:=0;
  p:=a;
  while a<>0 do
    begin
      //c:=c*10+a mod 10;
      if (a mod 10=7) then c:=c*10+1 else
      if (a mod 10=4) then c:=c*10+0;
      k:=k*10+c;
      //if (b mod 10=7) then c:=c*10+7 else
     // if (b mod 10=4) then c:=c*10+4;
      a:=a div 10;
      end;
     // while k<>0 do
   // begin
    //  g:=g*10+k mod 10;
      //if (c=1) then c:=7 else
      //if (c=0) then c:=4;
     // r:=r*10+g;
      //if (b mod 10=7) then c:=c*10+7 else
     // if (b mod 10=4) then c:=c*10+4;
     // k:=k div 10;
     // end;
     
     // writeln(i);
     //write(r1(inttostr(c*10+1)));
     u:=strtoint((inttostr(c*10+1)));
     if (u>100) then
     write(u) else 
      if (p>10) then write(u*10)
      else  if (p>20) then write(u*10+1) else
      if (u=11) then write(u*10);
  end.
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7816 / 4635 / 2837
Регистрация: 22.11.2013
Сообщений: 13,158
Записей в блоге: 1
12.11.2018, 13:53
Обращаю внимание, у вас на входе десятичное число может быть 32-значное.
1
 Аватар для Mikstereo
98 / 36 / 18
Регистрация: 05.11.2018
Сообщений: 231
12.11.2018, 13:54  [ТС]
Цитата Сообщение от bormant Посмотреть сообщение
Обращаю внимание, у вас на входе десятичное число может быть 32-значное.
Как тогда?
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7816 / 4635 / 2837
Регистрация: 22.11.2013
Сообщений: 13,158
Записей в блоге: 1
12.11.2018, 13:54
Первая часть элементарно делается на строках.
0
 Аватар для Mikstereo
98 / 36 / 18
Регистрация: 05.11.2018
Сообщений: 231
12.11.2018, 14:01  [ТС]
Цитата Сообщение от bormant Посмотреть сообщение
Обращаю внимание, у вас на входе десятичное число может быть 32-значное
И еще моя программа не всегда правильно переводит в 2-ю систему счисления,хотя вроде код правильный.

Добавлено через 3 минуты
Цитата Сообщение от bormant Посмотреть сообщение
Первая часть элементарно делается на строках.
Мой вариант,не работает для 32-х значных чисел,помогите
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function Lucky(n:int64):boolean;
begin
lucky:=true;
if (n=0) then exit else
  begin
    while n>0 do begin
      if (n mod 10<>4) and (n mod 10<>7) then Lucky:=false;
      n:=n div 10;
      end;
end;
end;
var n,i,k:int64;
begin
  read(n);
  k:=0;
  for n:=n downto n div 10 do
  begin
    if Lucky(n) then begin
     write(n,' ');
      exit;
    end;
    end;
end.
Добавлено через 2 минуты
Цитата Сообщение от Mikstereo Посмотреть сообщение
32-х значных чисел
Ну максимальное счастливое лежит в диапазоне n..n div 10,для целых чисел qword работает но 32-х значные числа не влазят в этот т
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7816 / 4635 / 2837
Регистрация: 22.11.2013
Сообщений: 13,158
Записей в блоге: 1
12.11.2018, 15:49
Думайте дальше, алгоритм расписан, реализуется тривиально.
Перебору тут не место.

Добавлено через 4 минуты
Вот ваше «число»: var s: String[32], придумайте как получить из него счастливое, это очень просто.
1
 Аватар для Mikstereo
98 / 36 / 18
Регистрация: 05.11.2018
Сообщений: 231
12.11.2018, 15:53  [ТС]
Можете хотя бы второй пункт алгоритма написать в паскале для 32-х значных чисел?

Добавлено через 3 минуты
Цитата Сообщение от bormant Посмотреть сообщение
это очень просто
Ну я уже писал, проверять для каждого числа на промежутке n..n div 10 является ли оно счастливым.
Способ 2 немного другой,для каждой цифры числа проверять(начиная с первой),
1.1) если цифра меньше 4,то в максимальном счастливом разрядов на 1 меньше,чем в исходном
1.2) если цифра равна 4,ничего не делаем,проверяем следующие числа
1.3) если цифра больше 4 но меньше 7,то присваиваем ей значение 4
1.4) если цифра больше 7 то присваиваем ей значение 7
1.5) если цифра равна 7 то проверяем следующие цифры.

Добавлено через 25 секунд
Цитата Сообщение от Mikstereo Посмотреть сообщение
является ли оно счастливым
первое найденное и будет максимальным счастливым
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7816 / 4635 / 2837
Регистрация: 22.11.2013
Сообщений: 13,158
Записей в блоге: 1
12.11.2018, 16:25
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var
  n, m: QWord;
  i: Integer;
begin
  ReadLn(s);
  { тут получаем счастливое число в s }
 
  m:=1;
  for i:=Length(s) downto 1 do begin
    if s[i]='7' then n:=n or m;
    m:=m shl 1;
  end;
  WriteLn(n or m-1);
end.
Добавлено через 19 минут
Про способ 2: как отправная точка пойдет, но в итоге будет несколько иначе.

Добавлено через 7 минут
проверять для каждого числа на промежутке n..n div 10
Сколько придется ждать перебора от 9*1032 до 8*1032 и еще чуть?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
12.11.2018, 16:25
Помогаю со студенческими работами здесь

Найти сумму и количество целых чисел, больших 10, меньших 30 и кратных 5
Найти сумму и количество целых чисел, больших 10, меньших 30 и кратных 5 массива М(25)

Найти количество положительных и отрицательных чисел среди чисел заданного вида
Найти количество положительных и отрицательных чисел среди чисел вида: sin x n при х=1,13; n=1…30

Вычислить произведение чисел, больших заданного D
Вычислить произведение чисел, больших заданного D и стоящих на местах, кратных 3; подсчитать также количество чисел, не равных заданному Х....

Посчитать количество отрицательных элементов массива, больших заданного значения
Задача такая. Дана матрица 10 на 10 и числа выводятся рандомно в диапазоне от -15 до 15. И надо посчитать количество отрицательных...

Найти количество четных чисел, сумма цифр в которых не превышает заданного числа P
Помогите пожалуйста решить задачу! Прикрепил.


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru