Форум программистов, компьютерный форум CyberForum.ru

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

Войти
Регистрация
Восстановить пароль
 
kalaider
0 / 0 / 0
Регистрация: 24.10.2012
Сообщений: 31
#1

Олимпиадная задача - C++

02.11.2012, 13:47. Просмотров 504. Ответов 8
Метки нет (Все метки)

Есть такая задачка:
В ряд выписаны числа, состоящие только из цифр 1, 3, 7: 1, 3, 7, 11, 13, 17, ...
Необходимо по номеру N определить число, находящееся на N-ном месте.

Я пробовал работать с системой счисления. Т.к. в записи числа используются три цифры, то система счисления троичная 1 - 1, 3 - 2, 7 - 3. Заменим, например, в числе 71 семерку тройкой. Тройки в троичной нет, поэтому получается число 101. 1013 = 1010. 10 - место числа 71. Вроде катит, но возникает проблема - нужно граммотно преобразовать 71.

Может есть другие способы?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
v.a.l.i.d
412 / 377 / 10
Регистрация: 21.09.2012
Сообщений: 913
02.11.2012, 14:35     Олимпиадная задача #2
у меня вот что получилось.
в комментарии написал последовательность этих чисел, если конечно я правильно ее понял.
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
29
30
31
#include "stdafx.h"
#include "iostream"
using namespace std;
 
int f(int n1, int n2)
{
    return n1*10 + n2;
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(LC_ALL, "Russian");
 
    // 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  
    // 1 3 7 | 11 13 17 | 21 23 27 | 31 33 37 | 41 43 47 | 51 53 57 | 61 63 67 | 71 73 77 | 81 83 87 | 91 93 97 | 101 103 107 |
 
    const int A[3] = {7, 1, 3};
    int N;
    int number;
 
    cout << "Введите число: ";
    cin >> N;
 
    number = f((N-1) / 3,  A[N % 3]);
 
    cout << "     N = " << N        << endl;
    cout << "number = " << number   << endl;
 
    system("pause");
    return 0;
}
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
02.11.2012, 14:37     Олимпиадная задача #3
Нет, вы не правильно поняли порядок чисел. В числе 21 используется двойка, а можно использовать только 1, 3 или 7.
Thinker
Эксперт C++
4219 / 2193 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.11.2012, 14:49     Олимпиадная задача #4
а что вам мешает перевести число N в троичную систему счисления, а затем заменить 0 на 1, 1 на 3, 2 на 7?
I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
02.11.2012, 14:51     Олимпиадная задача #5
Thinker, надо будет сделать небольшую поправку на первые три числа. Напрямую не прокатит.
Например N = 8 (если мы считаем, что 0 стоит на нулевой позиции)
В троичной это 22
Получаем 77, но должно быть 33
Thinker
Эксперт C++
4219 / 2193 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.11.2012, 15:00     Олимпиадная задача #6
точно, переводим число N-4 в троичную, а потом заменяем
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
02.11.2012, 15:08     Олимпиадная задача #7
I.M., мы должны понижать на один уровень.
если 0=1, 1=3, 2=7. То при получении 22 мы берем не 77, а 33.
при получении 1 мы берем не 3, а 1.
при получении 11 мы берем не 33, а 11.
Thinker
Эксперт C++
4219 / 2193 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.11.2012, 18:19     Олимпиадная задача #8
все, оказывается, просто, когда есть время немного подумать:
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
29
30
31
32
33
34
35
36
37
#include<stdio.h>
 
char s[1024];
void F(int n)
{
   int i = 0, j;
   char buf;
   do
   {
      n--;
      s[i++] = n % 3 + '0';
      n /= 3;
   }while(n);
   s[i] = '\0';
   for(j = i - 1, i = 0; i < j; i++, j--)
   {
      buf = s[i]; s[i] = s[j]; s[j] = buf;
   }
   for(i = 0; s[i]; i++)
      switch(s[i])
      {
         case '0': s[i] = '1'; break;
         case '1': s[i] = '3'; break;
         case '2': s[i] = '7'; break;
      };
}
 
int main()
{
   int i;
   for(i = 1; i < 50; i++)
   {
      F(i);
      puts(s);
   }
   return 0;
}
либо в таком виде
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
#include<stdio.h>
int a[1024];
 
int F(int x)
{
   return x == 0 ? 1 : (x == 1 ? 3 : 7);
}
 
void Search(int n)
{
   int i = 0;
   do
   {
      a[i++] = (--n) % 3;
      n /= 3;
   }while(n);
   for(i--; i >= 0; i--)
      printf("%d", F(a[i]));
   printf("\n");
}
 
int main()
{
   int i;
   for(i = 1; i < 50; i++)
      Search(i);
   return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2012, 22:29     Олимпиадная задача
Еще ссылки по теме:

C++ Олимпиадная задача. Рыбаки
C++ C++. Олимпиадная задача
Сладкая олимпиадная задача C++
Олимпиадная задача на перевертыши C++
C++ Олимпиадная задача

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

Или воспользуйтесь поиском по форуму:
kebal
9 / 9 / 0
Регистрация: 02.11.2012
Сообщений: 153
05.11.2012, 22:29     Олимпиадная задача #9
Мб уже и поздно, но можно ещё с рекурсией сделать. Кажется будет полегче.
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
void check(int l);
int b[80];
int main () {
    int n,i=0;
    cout<<"Vvedite chislo n: ";
    cin>>n;
    while(i<n){
    check(0);
    i++;
    }
    for(int t=79; t>=0; t--){
        if (b[t]!=0) cout<<b[t];
    }
    cout<<"\n";
system("pause");
return 0;
}
void check(int l){
    if(b[l]==0) b[l]=1;
    else if(b[l]==1) b[l]=3;
    else if (b[l]==3) b[l]=7;
    else if (b[l]==7) {
        check(l+1);
        b[l]=1;
    }
}
Yandex
Объявления
05.11.2012, 22:29     Олимпиадная задача
Ответ Создать тему
Опции темы

Текущее время: 23:13. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru