Задумано некоторое число

@airesjke · Регистрация: 30.10.2011

Author24 — интернет-сервис помощи студентам

Задумано некоторое число x (x<100). Известны числа k, m, n - остатки от деления этого числа на 3, 5, 7. Найти x

Комментарий модератора

Запрещено создавать темы с бессмысленными названиями вроде "Помогите!", "Вопрос" и т.п.

Байт · 19.11.2011, 11:35

C

for(x=0; x<100; x++) {
  if ((x%3)==k && (x%5)==m && (x%7)==n) {
    cout<<x;
    break;
  }
}
if (x==100) cout<<"Решения нет";

По китайской теореме об остатках решение не более чем одно.
Вот если x < 105 - тогда ровно одно.

@Hi4ko · 19.11.2011, 12:36

x<100 как бы намекает нам, что можно сделать это перебором
у нас есть 3 выражения:
$https://www.cyberforum.ru/cgi-bin/latex.cgi? x=3*a+k$
$https://www.cyberforum.ru/cgi-bin/latex.cgi? x=5*b+m$
$https://www.cyberforum.ru/cgi-bin/latex.cgi? x=7*c+n$
где a,b,c - натуральные числа или 0
$https://www.cyberforum.ru/cgi-bin/latex.cgi? a_M=100/3=33$
$https://www.cyberforum.ru/cgi-bin/latex.cgi? b_M=100/5=20$
$https://www.cyberforum.ru/cgi-bin/latex.cgi? c_M=100/7=14$
т.е в худшем случае будет $https://www.cyberforum.ru/cgi-bin/latex.cgi? 33*20*14=9240$ действий. Мало, значит можно решать перебором

C++

#include <iostream>
using namespace std;
int main()
{
int k,m,n;
cin>>k>>m>>n;
for(int a=0;a!=34;a++)
for(int b=0;b!=21;b++)
for(int c=0;c!=15;c++)
if(3*a+k==5*b+m && 3*a+k==7*c+n && 5*b+m==7*c+n)
{
cout<<3*a+k<<endl;
break;
}
}

@Thinker · 19.11.2011, 12:52

Если знаете китайскую теорему об остатках (теория чисел), то решите задачу легко и поймете, что решение в диапазоне от 0 до 104 единственно, поэтому не зря вас просят найти x при условии, что x<100

Вот вам получаемая формула:

x = (70*k + 21*m + 15*n) % 105;

C

#include<stdio.h>
 
int main()
{
   int k, m, n, x;
   scanf("%d%d%d", &k, &m, &n);
   x = (70*k + 21*m + 15*n) % 105; 
   printf("x = %d\n", x);
   return 0;
}

Байт · 19.11.2011, 16:59

Thinker, а первое слагаемое случаем не 35*k ?

@Thinker · 19.11.2011, 18:15

Сообщение от Байт

Thinker, а первое слагаемое случаем не 35*k ?

Неа) Применил алгоритм решения системы сравнений, где модули попарно различны и попарно взаимно просты (китайская теорема об остатках). Это удивительно, что числа 21 и 15 остались, а не то, что 35 изменилось))

Байт · 19.11.2011, 19:52

Сообщение от Thinker

Неа) Применил алгоритм решения системы сравнений, где модули попарно различны и попарно взаимно просты (китайская теорема об остатках). Это удивительно, что числа 21 и 15 остались, а не то, что 35 изменилось))

Тогда извиняйте. Это я из соображений симметрии. Подробно сам не смотрел, замучила текучка.

@Thinker · 19.11.2011, 20:28

Сообщение от Байт

замучила текучка

Не по теме:

не понял о чем вы. Гераклит тоже вот говорит:"Все течет, все меняется"

@Shman · 19.05.2012, 14:26

Я загадал число 20, остатки от деления этого числа на 3, 5 и 7 - это 3, 0, 6, соответсвенно. Но когда я ввожу эти числа в качестве k, m, n, программа ничего не выдает, ни 20 ни "Число не найдено". Где ошибка?

C++

#include <stdio.h>
#include <conio.h>
 
int main()
{
 int i, k, m, n; 
 
  printf ("Vvedite ostatok ot deleniya x na 3, k="); // Введите остаток от деления х на 3
  scanf ("%d", &k);
  printf ("Vvedite ostatok ot deleniya x na 5, m="); // Введите остаток от деления х на 5
  scanf ("%d", &m);
  printf ("Vvedite ostatok ot deleniya x na 7, n="); // Введите остаток от деления х на 7
  scanf ("%d", &n);
  
  for ( i=1; i <100; i++)
   {
    if ((i%3)==k && (i%5)==m && (i&7)==n)  // Если остаток от деления равен введеному числу, то...
     {  
      printf("\n x= %d", i); // напечатать его
      break;
     }
   if ((i%3)!=k && (i%5)!=m && (i&7)!=n) // Если остаток от деления НЕ равен введеному числу, то...
     {
      printf ("\n Chislo ne naydeno");   // напечатать "Число не найдено" 
      break;
     }   
   }  
 getch();
 return 0;
}

valeriikozlov · 19.05.2012, 14:41

вот так пробуйте:

C++

#include <stdio.h>
#include <conio.h>
 
int main()
{
 int i, k, m, n; 
 
  printf ("Vvedite ostatok ot deleniya x na 3, k="); // Введите остаток от деления х на 3
  scanf ("%d", &k);
  printf ("Vvedite ostatok ot deleniya x na 5, m="); // Введите остаток от деления х на 5
  scanf ("%d", &m);
  printf ("Vvedite ostatok ot deleniya x na 7, n="); // Введите остаток от деления х на 7
  scanf ("%d", &n);
  
  for ( i=1; i <100; i++)
   {
    if ((i%3)==k && (i%5)==m && (i%7)==n) 
     {  
      printf("\n x= %d", i);
      break;
     }
  }
   if ((i%3)!=k && (i%5)!=m && (i%7)!=n) 
     {
      printf ("\n Chislo ne naydeno");                    
     }   
   
 getch();
 return 0;
}

Сообщение от Shman

Я загадал число 20, остатки от деления этого числа на 3, 5 и 7 - это 3, 0, 6, соответсвенно.

И когда загадываете число 20, то вводите 2, 0, 6

@Shman · 19.05.2012, 14:56

valeriikozlov,
Убрали break в последнем if? Ввожу 2, 0, 6. Пишет 99 раз, что число не найдено.

valeriikozlov · 19.05.2012, 15:06

Вы не свой код правьте, Вы мой скопируйте себе и запускайте (я не только break убрал, еще и скобки поменял).

@Shman · 19.05.2012, 15:26

valeriikozlov, теперь понял, спасибо. А почему когда вводишь 1, 0, 2 ничего не выводится? Вообще ничего.

@grizlik78 · 19.05.2012, 15:41

Потому, что решением является 100, а в цикле проверяется последним 99. А после цикла проверяется как-раз 100, и поскольку остатки подходят, то и про не найденное число не сообщается.

valeriikozlov · 19.05.2012, 15:45

Сообщение от Shman

А почему когда вводишь 1, 0, 2 ничего не выводится? Вообще ничего.

просто число 100, которому равна переменная i после цикла, удовлетворяет как раз условию: остаток от деления на 3 равен 1, остаток от деления на 5 равен 0, остаток от деления на 7 равен 2. Тогда лучше так запускайте:

C++

#include <stdio.h>
#include <conio.h>
 
int main()
{
 int i, k, m, n; 
 
  printf ("Vvedite ostatok ot deleniya x na 3, k="); // Введите остаток от деления х на 3
  scanf ("%d", &k);
  printf ("Vvedite ostatok ot deleniya x na 5, m="); // Введите остаток от деления х на 5
  scanf ("%d", &m);
  printf ("Vvedite ostatok ot deleniya x na 7, n="); // Введите остаток от деления х на 7
  scanf ("%d", &n);
  
  for ( i=1; i <100; i++)
   {
    if ((i%3)==k && (i%5)==m && (i%7)==n) 
     {  
      printf("\n x= %d", i);
      break;
     }
  }
   if (i==100) 
     {
      printf ("\n Chislo ne naydeno");                    
     }   
   
 getch();
 return 0;
}

@Shman · 19.05.2012, 15:59

valeriikozlov,
Тогда уж позволить вручную устанавливать мин и макс границу интервала и добавить if i>=max:

C++

#include <stdio.h>
#include <conio.h>
 
int main()
{
 int i, min, max, k, m, n; 
  printf ("Vvedite min x intervala, min x="); // Введите минимальный x интервала
  scanf ("%d", &min); 
  printf ("Vvedite max x intervala, max x="); // Введите максимальный x интервала
  scanf ("%d", &max); 
  printf ("Vvedite ostatok ot deleniya x na 3, k="); // Введите остаток от деления х на 3
  scanf ("%d", &k);
  printf ("Vvedite ostatok ot deleniya x na 5, m="); // Введите остаток от деления х на 5
  scanf ("%d", &m);
  printf ("Vvedite ostatok ot deleniya x na 7, n="); // Введите остаток от деления х на 7
  scanf ("%d", &n);
  
  for ( i=min; i <max; i++)
   {         
    if ((i%3)==k && (i%5)==m && (i%7)==n)  // Если остаток от деления равен введеному числу, то...
     {  
      printf("\n x= %d", i); // напечатать его
      break;
     }
  }
   if ((i%3)!=k && (i%5)!=m && (i%7)!=n && i>=max)   // Если остаток от деления НЕ равен введеному числу, то..
     {
      printf ("\n Chislo ne naydeno");  // напечатать "Число не найдено" 
     }
        
 getch();
 return 0;
}

@grizlik78 · 19.05.2012, 16:07

Shman, тогда если будет задумано число max, то программа опять ничего не выведет (при условии, что в цикле меньше 105 итераций)

Добавлено через 47 секунд

C++

1	if (i==max)

@Shman · 19.05.2012, 16:31

grizlik78, тогда как ограничить ввод неправильных значений? чтобы при вводе 0>x>104 выводилось сообщение о недопустимости ввода?

@grizlik78 · 19.05.2012, 16:33

А в этом месте не понял. Вводятся же остатки, а число загадывается.

@Shman · 19.05.2012, 17:30

C++

#include <stdio.h>
#include <conio.h>
 
int main()
{
 int i, k, m, n; 
   printf ("Vvedite ostatok ot deleniya x na 3, k="); // Введите остаток от деления х на 3
   scanf ("%d", &k);
   printf ("Vvedite ostatok ot deleniya x na 5, m="); // Введите остаток от деления х на 5
   scanf ("%d", &m);
   printf ("Vvedite ostatok ot deleniya x na 7, n="); // Введите остаток от деления х на 7
   scanf ("%d", &n);
  
  for (i=0; i<104; i++)
   {         
    if ((i%3)==k && (i%5)==m && (i%7)==n)  // Если остаток от деления равен введеному числу, то...
     {  
      printf("\n x= %d", i); // напечатать его
      break;
     }
  }
   if ((i%3)!=k && (i%5)!=m && (i%7)!=n)   // Если остаток от деления НЕ равен введеному числу, то..
     {
      printf ("\n Chislo ne naydeno");  // напечатать "Число не найдено" 
     }
   if ((i>=104))  // Если загаданое число больше допустимого диапазона, то..
     {
      printf ("\n Chislo ne naydeno");  // напечатать "Число не найдено" 
     }
        
 getch();
 return 0;
}

Вот! Тогда если число будет больше допустимого диапазона выведется сообщение о том, что число не найдено. Проверил на 1, 0, 2.

Добавлено через 51 минуту

C++

   if ((i%3)!=k && (i%5)!=m && (i%7)!=n || (i>=104))   // Если остаток от деления НЕ равен введеному числу...
     {                                                // или загаданое число больше допустимого диапазона, тогда..
      printf ("\n Chislo ne naydeno!");  // напечатать "Число не найдено" 
     }

Компактнее

@Shman 6 / 6 / 6 Регистрация: 30.04.2012 Сообщений: 216
	19.05.2012, 15:26	13
	valeriikozlov, теперь понял, спасибо. А почему когда вводишь 1, 0, 2 ничего не выводится? Вообще ничего. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	19.11.2011, 16:59	5
	Thinker, а первое слагаемое случаем не 35*k ? 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	19.11.2011, 18:15	6
	Сообщение от Байт Thinker, а первое слагаемое случаем не 35*k ? Неа) Применил алгоритм решения системы сравнений, где модули попарно различны и попарно взаимно просты (китайская теорема об остатках). Это удивительно, что числа 21 и 15 остались, а не то, что 35 изменилось)) 1

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	19.11.2011, 19:52	7
	Сообщение от Thinker Неа) Применил алгоритм решения системы сравнений, где модули попарно различны и попарно взаимно просты (китайская теорема об остатках). Это удивительно, что числа 21 и 15 остались, а не то, что 35 изменилось)) Тогда извиняйте. Это я из соображений симметрии. Подробно сам не смотрел, замучила текучка. 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	19.11.2011, 20:28	8
	Сообщение от Байт замучила текучка Не по теме: не понял о чем вы. Гераклит тоже вот говорит:"Все течет, все меняется" 0

@Shman 6 / 6 / 6 Регистрация: 30.04.2012 Сообщений: 216
	19.05.2012, 14:56	11
	valeriikozlov, Убрали break в последнем if? Ввожу 2, 0, 6. Пишет 99 раз, что число не найдено. 0

valeriikozlov 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	19.05.2012, 15:06	12
	Вы не свой код правьте, Вы мой скопируйте себе и запускайте (я не только break убрал, еще и скобки поменял). 0

@grizlik78 2381 / 1665 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	19.05.2012, 15:41	14
	Потому, что решением является 100, а в цикле проверяется последним 99. А после цикла проверяется как-раз 100, и поскольку остатки подходят, то и про не найденное число не сообщается. 0

@Shman 6 / 6 / 6 Регистрация: 30.04.2012 Сообщений: 216
	19.05.2012, 16:31	18
	grizlik78, тогда как ограничить ввод неправильных значений? чтобы при вводе 0>x>104 выводилось сообщение о недопустимости ввода? 0

@grizlik78 2381 / 1665 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	19.05.2012, 16:33	19
	А в этом месте не понял. Вводятся же остатки, а число загадывается. 0

Задумано некоторое число

Решение