54 / 54 / 2
Регистрация: 20.01.2013
Сообщений: 832
Записей в блоге: 1
1

Задача 1, 10, 100, 1000

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

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

Не могу понять как её решить Подскажите.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.03.2013, 00:02
Ответы с готовыми решениями:

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

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

При вводе цифр 1,5,10,50,100,500,1000 покажет на мониторе римские цифры
Помогите пожалуйста написать программу: которая при вводе цифр 1,5,10,50,100,500,1000 выводиться...

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

13
Эксперт С++
4722 / 2543 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
05.03.2013, 06:14 2
Цитата Сообщение от HardLogin Посмотреть сообщение
Подскажите.
берете массив типа int (мне хватило размера 65536). Заполняете его числами: 1, 2, 4, 7 и т.д. Т.е. значениями на каких местах в последовательности находятся единицы. Потом для каждого Ki двоичный поиск. Если число Ki найдено, то выводите 1, если нет, то выводите 0.
1
Диссидент
Эксперт C
26836 / 16744 / 3667
Регистрация: 24.12.2010
Сообщений: 37,481
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
54 / 54 / 2
Регистрация: 20.01.2013
Сообщений: 832
Записей в блоге: 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
1 / 1 / 1
Регистрация: 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
54 / 54 / 2
Регистрация: 20.01.2013
Сообщений: 832
Записей в блоге: 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
1 / 1 / 1
Регистрация: 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
Для продолжения нажмите любую клавишу . . .
какая у вас ОС и компилятор?
Миниатюры
Задача 1, 10, 100, 1000  
0
54 / 54 / 2
Регистрация: 20.01.2013
Сообщений: 832
Записей в блоге: 1
05.03.2013, 15:59  [ТС] 8
не там нужно вывести только одну n цифр 0 или 1
0
Эксперт С++
4722 / 2543 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
05.03.2013, 19:50 9
Цитата Сообщение от HardLogin Посмотреть сообщение
и то медленно: 0.25 сек.
Почему же медленно? Там ограничения 1 сек.
Правда мой вариант (пост №2) отработал за 0.062 сек. Если есть желание реализуйте его. Не получится покажите свой код, помогу.
0
54 / 54 / 2
Регистрация: 20.01.2013
Сообщений: 832
Записей в блоге: 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
Эксперт С++
4722 / 2543 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
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
54 / 54 / 2
Регистрация: 20.01.2013
Сообщений: 832
Записей в блоге: 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
_
317 / 151 / 27
Регистрация: 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
54 / 54 / 2
Регистрация: 20.01.2013
Сообщений: 832
Записей в блоге: 1
06.03.2013, 20:22  [ТС] 14
как отсюда n*(n-1)/2 + 1 может выйти такое 8*m-7 ? причем тут 8 и 7?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.03.2013, 20:22
Помогаю со студенческими работами здесь

Даны 100 целых чисел, принадлежащих интервалу [0; 1000]. Определите количество тех из них, которые делятся на
Даны 100 целых чисел, принадлежащих интервалу . Определите количество тех из них, которые делятся...

Реализовать цикличный вывод строки (10, 100, 1000 циклов) в нескольких потоках (2, 4, 8, 16)
Необходимо реализовать вывод строки в нескольких потоках (2, 4, 8, 16 потоков) с помощью функций...

Timus. Задача 1209. 1, 10, 100, 1000
Сразу скажу что на данном форуме с данной задачей я прочитал штук 5 тем. Но в каких то нет отличий...

Вывод в Excel значения в пределах от 100 до 1000 с шагом 100 в столбец
Написать VBS-скрипт, выводящий в Excel значения в пределах от 100 до 1000 с шагом 100 в столбец. ...

Записать 1000 случайных чисел в диапазоне (-100, 100)
Записать 1000 случайных чисел в диапазоне (-100,100) в файл а.txt . В файл otr.txt вывести...

Вывести числа от 100 до 1000 с шагом 100.
Привет. Помогите. Нужно составить программу на языке паскаль, используя опереатор цикла. Нужно...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru