С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 800
Записей в блоге: 1
#1

Задача 1, 10, 100, 1000 - C++

05.03.2013, 00:02. Просмотров 1320. Ответов 13
Метки нет (Все метки)

Представим себе бесконечную последовательность цифр, составленную из записанных друг за другом возрастающих степеней десятки. Вот начало этой последовательности: 110100100010000… Всё, что надо — определить, какая цифра находится в такой последовательности на определённом месте.
Исходные данные
В первой строке находится целое число N (1 ≤ N ≤ 65535). В i-й из N последующих строк записано целое число Ki — номер позиции в последовательности (1 ≤ Ki ≤ 231 − 1).
Результат
Выведите через пробел N цифр. i-я цифра должна равняться цифре, которая находится в описанной выше последовательности на позиции с номером Ki.

Не могу понять как её решить Подскажите.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.03.2013, 00:02
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача 1, 10, 100, 1000 (C++):

Нужно вычислить факториал 33, 100 и 1000 как можно проще - C++
Нужно вычислить фактариал 33, 100 и 1000 как можно проще

Найти все простые числа из интервала от 100 до 1000, используя логическую функцию - C++
Нужно написать программу, буду премного благодарен) Знаю, что на самом деле тут всё просто, но я только начал учиться и пока не совсем...

Разработать программу, которая динамически выделяет 100 блоков памяти по 1000 байт каждый и освобождает их - C++
Всем привет. Подкинули на учебе вот такое задание - Напишите программу, которая динамически выделяет 100 блоков памяти по 1000 байт каж-дый...

Даны 100 целых чисел, принадлежащих интервалу [0; 1000]. Определите количество тех из них, которые делятся на - C++
Даны 100 целых чисел, принадлежащих интервалу . Определите количество тех из них, которые делятся на 7. 241; 488; 149; 893; 622; 793;...

Составить таблицу стоимости порций сыра весом 50, 100, 150, … 1000 г. Стоимость сыра — вводимая величина. - C++
Буду очень признателен, если поможете безрукому... 3. Составить таблицу стоимости порций сыра весом 50, 100, 150, … 1000 г. Стоимость...

Покупатель должен заплатить в кассу 5 руб. У него имеются купюры по 1, 5, 10, 50, 100, 500, 1000 и 10000 руб - C++
Покупатель должен заплатить в кассу 5 руб. У него имеются купюры по 1, 5, 10, 50, 100, 500, 1000 и 10000 руб. Сколько купюр разного...

13
valeriikozlov
Эксперт С++
4676 / 2502 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.03.2013, 06:14 #2
Цитата Сообщение от HardLogin Посмотреть сообщение
Подскажите.
берете массив типа int (мне хватило размера 65536). Заполняете его числами: 1, 2, 4, 7 и т.д. Т.е. значениями на каких местах в последовательности находятся единицы. Потом для каждого Ki двоичный поиск. Если число Ki найдено, то выводите 1, если нет, то выводите 0.
1
Байт
Нарушитель
Эксперт C
16696 / 10960 / 1689
Регистрация: 24.12.2010
Сообщений: 21,388
05.03.2013, 07:24 #3
А можно без всяких массивов.
Единицы стоят на местах n*(n-1)/2 + 1
C
1
2
3
4
5
6
 int F(int k)
{ int s, i; 
  for(s=i=1; s<k; i++) s+=i;
  if (s==k) return 1;
  else return 0;
}
0
HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 800
Записей в блоге: 1
05.03.2013, 09:27  [ТС] #4
выдает Time limit exceeded вот код:
C++
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
#include <iostream>
using namespace std;
 
int F(int k)
{ int s, i; 
  for(s=i=1; s<k; i++) s+=i;
  if (s==k) return 1;
  else return 0;
}
 
int main()
{
int n;
cin >> n;
 
int *k = new int[ n ];
for( int i = 0; i < n; i++ )
cin >> k[ i ];
 
int s;
for( int i = 0; i < n; i++ )
{
 cout << F( k[ i ] ) << (( i == n - 1 )? "" : " ");
}
 
return 0;
}
0
pontakrin
1 / 1 / 0
Регистрация: 22.03.2010
Сообщений: 71
05.03.2013, 13:15 #5
не знаю понял ли вопрос но вот

C++
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
using namespace std;
 
 
int main(void){
    char * ch = "110100100010000";
    char buf[255];
    int pos = 0; // позиция
    int bi = 1;
 
    for (int i = 0; i < strlen(ch); i++){   // ищем цыфры
        
        if (ch[i] == '1'){
            ++pos;
            cout << pos << ". ";
            
            for (int j = i; j < strlen(ch); j++){
                if (ch[j] == '1'){
                    buf[bi] = 0;
                    memcpy(buf, &ch[j], bi++);
                    cout << buf << endl;
                    break;      
                }
            }
        }
    }
   
   return 0;
}
0
HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 800
Записей в блоге: 1
05.03.2013, 14:12  [ТС] #6
не работает(

Добавлено через 2 минуты
вобщем я там нашел решение но я не понимаю как оно работает(
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
long float m,n;
int N;
    cin>>N;
    for  (int i=1; i<=N; i++)
    {
    cin>>m;
    n=(1+sqrt(8*m-7))/2;
 if((1+sqrt(8*m-7))/2==floor((1+sqrt(8*m-7))/2))
   cout<<1<<" ";
    else
    cout<<0<<" ";
     }
    cin>>N;
    return 0;
    }
и то медленно: 0.25 сек.
0
pontakrin
1 / 1 / 0
Регистрация: 22.03.2010
Сообщений: 71
05.03.2013, 14:13 #7
у меня нормально собралось.

C++
1
2
3
4
5
6
1. 1
2. 10
3. 100
4. 1000
5. 10000
Для продолжения нажмите любую клавишу . . .
какая у вас ОС и компилятор?
0
Миниатюры
Задача 1, 10, 100, 1000  
HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 800
Записей в блоге: 1
05.03.2013, 15:59  [ТС] #8
не там нужно вывести только одну n цифр 0 или 1
0
valeriikozlov
Эксперт С++
4676 / 2502 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.03.2013, 19:50 #9
Цитата Сообщение от HardLogin Посмотреть сообщение
и то медленно: 0.25 сек.
Почему же медленно? Там ограничения 1 сек.
Правда мой вариант (пост №2) отработал за 0.062 сек. Если есть желание реализуйте его. Не получится покажите свой код, помогу.
0
HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 800
Записей в блоге: 1
05.03.2013, 22:12  [ТС] #10
ну вот же
C++
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
#include <iostream>
using namespace std;
 
int F(int k)
{ int s, i; 
  for(s=i=1; s<k; i++) s+=i;
  if (s==k) return 1;
  else return 0;
}
 
int main()
{
int n;
cin >> n;
 
int *k = new int[ n ];
for( int i = 0; i < n; i++ )
cin >> k[ i ];
 
int s;
for( int i = 0; i < n; i++ )
{
 cout << F( k[ i ] ) << (( i == n - 1 )? "" : " ");
}
 
return 0;
}
0
valeriikozlov
Эксперт С++
4676 / 2502 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.03.2013, 06:43 #11
Цитата Сообщение от HardLogin Посмотреть сообщение
ну вот же
это совсем не то )

Цитата Сообщение от valeriikozlov Посмотреть сообщение
берете массив типа int (мне хватило размера 65536). Заполняете его числами: 1, 2, 4, 7 и т.д. Т.е. значениями на каких местах в последовательности находятся единицы. Потом для каждого Ki двоичный поиск. Если число Ki найдено, то выводите 1, если нет, то выводите 0.
Нужно создать массив L[] размером 65536.
Затем нужно заполнить массив L[] числами: 1, 2, 4, 7, 11, 16 и т.д.
Потом уже считывая очередное ki искать его значение в массиве L[] (с помощью двоичного поиска). Если нашли это значение, то выводите 1, если не нашли, то выводите 0.
Снова считываете очередное ki и опять ищите его в массиве L[]...
0
HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 800
Записей в блоге: 1
06.03.2013, 09:34  [ТС] #12
ну понимаете это всем известный прием) но его можно получить, только написав программу которая может вычислить, без готовых решений, как я там писал:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <math.h>
using namespace std;
int main()
{
long float m,n;
int N;
    cin>>N;
    for  (int i=1; i<=N; i++)
    {
    cin>>m;
    n=(1+sqrt(8*m-7))/2;
 if((1+sqrt(8*m-7))/2==floor((1+sqrt(8*m-7))/2))
   cout<<1<<" ";
    else
    cout<<0<<" ";
     }
    cin>>N;
    return 0;
    }
этот код выложил какой то англичанин там на обсуждении задачи, он работает, но почему в чем подкол этой формулы:
C++
1
if((1+sqrt(8*m-7))/2==floor((1+sqrt(8*m-7))/2))
0
ya_noob
_
203 / 147 / 9
Регистрация: 08.10.2011
Сообщений: 432
06.03.2013, 11:21 #13
Цитата Сообщение от HardLogin Посмотреть сообщение
но почему в чем подкол этой формулы:
Вам же написали как можно вычислить местонахождение единиц:
Цитата Сообщение от Байт Посмотреть сообщение
Единицы стоят на местах n*(n-1)/2 + 1
8*m-7 - дискриминант квадратного уравнения, полученного из вышеприведенной формулы,
1+sqrt(8*m-7) - один из его корней
а эта штука
C++
1
if((1+sqrt(8*m-7))/2==floor((1+sqrt(8*m-7))/2))
проверяет является ли корень целым числом. Элементарно! Внимательней читайте сообщения и вникайте
0
HardLogin
52 / 52 / 1
Регистрация: 20.01.2013
Сообщений: 800
Записей в блоге: 1
06.03.2013, 20:22  [ТС] #14
как отсюда n*(n-1)/2 + 1 может выйти такое 8*m-7 ? причем тут 8 и 7?
0
06.03.2013, 20:22
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.03.2013, 20:22
Привет! Вот еще темы с ответами:

Задача простая Года n<=100 - C++
Дано натуральне число n(n&lt;=100), яке визначає вік людини ( в роках). Дати для цього числа найменування «років», «рік», «роки»: наприклад, 1...

Массив размерностью 30 заполнить случайными числами, лежащими в диапозоне от -100 до 100 - C++
Массив размерностью 30 заполнить случайными числами, лежащими в диапозоне от -100 до 100. Заменить все элементы с отрицательными значениями...

Вывести на экран таблицу стоимости яблок в диапозоне от 100 г. до 1 кг. с шагом 100 г - C++
Написать программу, которая выводит на экран таблицу стоимости, например, яблок в диапозоне от 100 г. до 1 кг. с шагом 100 г. Ниже приведён...

Генерировать и вывести на экран массив с целого числа n случайных чисел от -100 до 100 - C++
Генерировать и вывести на экран массив с целого числа n случайных чисел от -100 до 100. Число n вводит пользователь. Последний...


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

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

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