задачf на комбинаторику - Помощь студентам

sheff123 · 06.11.2011, 01:51

Определить количество чисел состоящих из n десятичных разрядов (n –
натуральное число, вводится пользователем, n <= 10) произведение цифр
которого равно числу K (натуральное число, вводится пользователем, K <
9n). Учитывать, что число может начинаться с нулей: 0042345
код на C)

NetSpace · 06.11.2011, 09:36

т.е. например, число 345, 354, 435, 453 ,543, 534 - при перемножнении их разрядов 5*4*3 = 60 - они все дадут одно и то же самое число.
далее, получаестя, вам необходимо узнать сколько вообще в числе разрядов, например, в числе 1000 их 4, а в нашем случае, скажем, 345 - их всего 3 (т.к. всего 3 цифры в числе). тогда таких чисел будет всего 3! = 6 (смотрите верхний ряд чисел и считайте). Ответ: всего 6 чисел, состоящих из 3 разрядов дадут такой вот результат. Факториал надо использовать, если я правильно понял задачу...

sheff123 · 06.11.2011, 11:25

Цитата:

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

т.е. например, число 345, 354, 435, 453 ,543, 534 - при перемножнении их разрядов 5*4*3 = 60 - они все дадут одно и то же самое число.
далее, получаестя, вам необходимо узнать сколько вообще в числе разрядов, например, в числе 1000 их 4, а в нашем случае, скажем, 345 - их всего 3 (т.к. всего 3 цифры в числе). тогда таких чисел будет всего 3! = 6 (смотрите верхний ряд чисел и считайте). Ответ: всего 6 чисел, состоящих из 3 разрядов дадут такой вот результат. Факториал надо использовать, если я правильно понял задачу...

для одноразрядного максимальное произведение 9 при том что само число N=9;
для двухразрядного максимальное произведение 81(9^2) при комбинации цисла 9*9=81(оно максимальное 2-разрядное) а минимальное для -х разрядов 11.
для трехразрядного максимальное произведение 729(9^3) число 9*9*9=729.
ну и т.д
т.е число К варьируется для каждого разряда в пределах возможных произведений.
P.S. трехзначные
для К=61 сколько комбинаций?? по моему 0.
для К=62 0
для к=63 373 733 337 971 791 197 179 917 3*7*3=63 ответ: для К=63 чисел будет 8.

sheff123 · 07.11.2011, 11:30

Решил её, не красиво получилось, код огромный да и думаю есть способ полегче:

Код:

#include <stdio.h>
#include <locale.h>
#include <math.h>


int main(int argc, char *argv[])
{   setlocale(LC_ALL,"");
	int n,k,a,b,c,d,e,f,g,h,j,l,kol=0;
	int flag;
	printf("Введите разрядность числа N");
	scanf("%d",&n);
	printf("Введите число К<(9^N)\n");
	scanf("%d",&k);
if (k>0) {flag=0;}
				 else {flag=1;};
	switch(n)
	{ case 1: { for(int i=1;i<10;i++)
				{if (i==k){kol++;}
			    
			    }break;}



      case 2: { for(int i=10;i<100;i++)
				{ a=i/10;
				  b=i%10;
				 
				  if ((a!=0) && (b!=0) && (k==a*b)&& (flag==0)) { kol++; printf("Число:%d\n",i);}
				  else { if ((a==0) || (b==0)&& (flag==1)) { kol++; printf("Число:%d\n",i);};}
			    
			    }break;}



	  case 3: { for(int i=100;i<1000;i++)
				{ a=(i/100);
				  b=((i%100)/10);
				  c=(i%10);
				
				  if ((flag==0) && (a!=0) && (b!=0) && (c!=0) && (k==(a*b*c))) { kol++; printf("Число:%d\n",i);};
				  if ((flag==1)&&((a==0) || (b==0)|| (c==0))) { kol++; printf("Число:%d\n",i);};
			    
			    }break;}




	  case 4: { for(int i=1000;i<10000;i++)
				{ a=(i/1000);
				  b=((i/100)%10);
				  c=((i%100)/10);
				  d=i%10;
				
				  if ((flag==0) && (a!=0) && (b!=0) && (c!=0) && (d!=0)&& (k==(a*b*c*d))) { kol++; printf("Число:%d\n",i);};
				  if ((flag==1)&&((a==0) || (b==0)|| (c==0)|| (d==0))) { kol++; printf("Число:%d\n",i);};
			    
			    }break;}
	
      case 5: { for( int i=10000;i<100000;i++)
				{ a=(i/10000);
				  b=((i/1000)%10);
				  c=((i/100)%10);
				  d=((i%100)/10);
				  e=(i%10);
				
				  if ((flag==0) && (a!=0) && (b!=0) && (c!=0) && (d!=0)&&(e!=0)&& (k==(a*b*c*d*e))) { kol++; printf("Число:%d\n",i);};
				  if ((flag==1)&&((a==0) || (b==0)|| (c==0)|| (d==0)|| (e==0))) { kol++; printf("Число:%d\n",i);};
			    
			    }break;}


              case 6: { for( int i=100000;i<1000000;i++)
				{ a=(i/100000);
				  b=((i/10000)%10);
				  c=(i/1000)%10;
				  d=((i/100)%10);
				  e=((i/10)%10);
                  f=(i%10);
				
				  if ((flag==0) && (a!=0) && (b!=0) && (c!=0) && (d!=0)&& (e!=0)&& (f!=0 )&& (k==(a*b*c*d*e*f))) { kol++; printf("Число:%d\n",i);};
				  if ((flag==1)&&((a==0) || (b==0)|| (c==0)|| (d==0)|| (e==0)|| (f==0))) { kol++; printf("Число:%d\n",i);};
			    
			    }break;}
		

              case 7: { for( int i=1000000;i<10000000;i++)
				{ a=(i/1000000);
				  b=((i/100000)%10);
				  c=((i/10000)%10);
				  d=((i/1000)%10);
                  e=((i/100)%10);
                  f=((i/10)%10);
				  g=(i%10);
				
				  if ((flag==0) && (a!=0) && (b!=0) && (c!=0) && (d!=0)&& (e!=0)&& (f!=0)&& (g!=0)&& (k==(a*b*c*d*e*f*g))) { kol++; printf("Число:%d\n",i);};
				  if ((flag==1)&&((a==0) || (b==0)|| (c==0)|| (d==0)|| (e==0)|| (f==0)|| (g==0))) { kol++; printf("Число:%d\n",i);};
			    
			    }break;}


                case 8: { for (int i=10000000;i<100000000;i++)
				{ a=(i/10000000);
				  b=((i/1000000)%10);
				  c=((i/100000)%10);
				  d=((i/10000)%10);
                  e=((i/1000)%10);
                  f=((i/100)%10);
				  g=((i/10)%10);
				  h=(i%10);
				
				  if ((flag==0) && (a!=0) && (b!=0) && (c!=0) && (d!=0)&& (e!=0)&& (f!=0)&& (g!=0)&& (h!=0)&&(k==(a*b*c*d*e*f*g*h))) { kol++; printf("Число:%d\n",i);};
				  if ((flag==1)&&((a==0) || (b==0)|| (c==0)|| (d==0)|| (e==0)|| (f==0)|| (g==0)|| (h==0))) { kol++; printf("Число:%d\n",i);};
			    
			    }break;}


                case 9: { for(int i=100000000;i<1000000000;i++)
				{ a=(i/100000000);
				  b=((i/10000000)%10);
				  c=((i/1000000)%10);
				  d=((i/100000)%10);
                  e=((i/10000)%10);
                  f=((i/1000)%10);
				  g=((i/100)%10);
				  h=((i/10)%10);
				  j=(i%10);
				
				  if ((flag==0) && (a!=0) && (b!=0) && (c!=0) && (d!=0)&& (e!=0)&& (f!=0)&& (g!=0)&& (h!=0)&& (j!=0)&&(k==(a*b*c*d*e*f*g*h*j))) { kol++; printf("Число:%d\n",i);};
				  if ((flag==1)&&((a==0) || (b==0)|| (c==0)|| (d==0)|| (e==0)|| (f==0)|| (g==0)|| (h==0) || (j==0))) { kol++; printf("Число:%d\n",i);};
			    
			    }break;}



              case 10: { for( int i=1000000000;i<10000000000;i++)
				{ a=(i/1000000000);
				  b=((i/100000000)%10);
				  c=((i/10000000)%10);
				  d=((i/1000000)%10);
				  e=((i/100000)%10);
                  f=((i/10000)%10);
				  g=((i/1000)%10);
				  h=((i/100)%10);
				  j=((i/10)%10);
				  l=(i%10);
				
				  if ((flag==0) && (a!=0) && (b!=0) && (c!=0) && (d!=0)&& (e!=0)&& (f!=0)&& (g!=0)&& (h!=0)&& (j!=0)&& (l!=0)&&(k==(a*b*c*d*e*f*g*h*j*l))) { kol++; printf("Число:%d\n",i);};
				  if ((flag==1)&&((a==0) || (b==0)|| (c==0)|| (d==0)|| (e==0)|| (f==0)|| (g==0)|| (h==0) || (j==0)|| (l==0))) { kol++; printf("Число:%d\n",i);};
			    
			    }break;}
     
	}
    printf("Количество чисел: %d\n",kol);
    return 0;
}

Serge_Bliznykov · 07.11.2011, 11:41

Цитата:

Решил её, не красиво получилось, код огромный да и думаю есть способ полегче:

ОМГ.

а не проще ли сделать следующее:

цикл от 1 до (10^N-1) (10 в степени N элементарно найти)
внутри цикла вызывать процедурку, которая РАСКЛАДЫВАЕТ число на отдельные цифры ( с помощью получения целого остатка от деления на 10 и целочисленного деления исходного числа на 10). получаемые цифры перемножаются. Полученное произведение функция возвращает.
если оно совпадает с числом K - увеличиваем счётчик на 1.
Всё.

p.s. я бы написал готовый код, благо что его всего пяток строк.. но, к сожалению и стыду своему, C/С++ совсем не знаю...

val_nnm · 07.11.2011, 13:50

В принципе задачу можно решить и оптимальным образом (перебирая несколько тысяч вариантов вместо миллиардов).
Для начала, число K нужно разложить на простые числа в диапазоне от 2 до 9 (т.е. 2, 3, 5, 7)
Скажем, количество каждых сомножителей запишем в массив A[]. Т.е. A[2] – количество вхождений числа 2 в разложение числа K.
Такое разложение будет единственным.
Дальше нужно проверить несколько вариантов
две двойки могут дать цифру 4
две тройки могут дать цифру 9
тройка и двойка могут дать цифру 6
(остальные варианты не проверяем т.к. они дают числа большие 9)
Т.е. сделать примерно такой цикл

Код:

For (int i4=0;i4++;i4<=A[2]/2)
{
  A[2] -= i4*2;
  A[4] += 1;
  For (int i9=0;i9++;i9<A[3]/2)
  {
    A[3]-=i9*2;
    A[9]+=1;
    For (int i6=0;i6++;i6<min(A[2],A[3]))
    {
      A[6]+=1;
      A[2]-=i6;
      A[3] -= i6;
      // Здесь в массиве A мы получаем варианты цифр из которых будет состоять искомые числа
      A[3] +=i6;
      A[2] +=i6;
      A[6] -=1;
    }
    A[9]-=1;
    A[3]+=i9*2;
  }
  A[4]-=1;
  A[2] += i4*2;
}

Дальше для каждого варианта разложения
Рассчитываем, сколькими вариантами эти цифры можно уложить для 1 значного числа для 2х значного числа и.т.д. до n (вернее i = A[2]+A[3]+A[4]+A[5]+A[6]+A[6]+A[8]+A[9] до n) считаем что числа в незаполненных позициях равны 1, но само число с 1 не начинаеться. Также проверяем вариант, что если число начинается с единиц. То количество вариантов умножается на это количество единиц, т.е. умножаем на n-i+1 (т.к. начальные единицы могут быть нулями по условию)

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

sheff123 · 07.11.2011, 16:46

Цитата:

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

В принципе задачу можно решить и оптимальным образом (перебирая несколько тысяч вариантов вместо миллиардов).
Для начала, число K нужно разложить на простые числа в диапазоне от 2 до 9 (т.е. 2, 3, 5, 7)
Скажем, количество каждых сомножителей запишем в массив A[]. Т.е. A[2] – количество вхождений числа 2 в разложение числа K.
Такое разложение будет единственным.
Дальше нужно проверить несколько вариантов
две двойки могут дать цифру 4
две тройки могут дать цифру 9
тройка и двойка могут дать цифру 6
(остальные варианты не проверяем т.к. они дают числа большие 9)
Т.е. сделать примерно такой цикл

Код:

For (int i4=0;i4++;i4<=A[2]/2)
{
  A[2] -= i4*2;
  A[4] += 1;
  For (int i9=0;i9++;i9<A[3]/2)
  {
    A[3]-=i9*2;
    A[9]+=1;
    For (int i6=0;i6++;i6<min(A[2],A[3]))
    {
      A[6]+=1;
      A[2]-=i6;
      A[3] -= i6;
      // Здесь в массиве A мы получаем варианты цифр из которых будет состоять искомые числа
      A[3] +=i6;
      A[2] +=i6;
      A[6] -=1;
    }
    A[9]-=1;
    A[3]+=i9*2;
  }
  A[4]-=1;
  A[2] += i4*2;
}

Дальше для каждого варианта разложения
Рассчитываем, сколькими вариантами эти цифры можно уложить для 1 значного числа для 2х значного числа и.т.д. до n (вернее i = A[2]+A[3]+A[4]+A[5]+A[6]+A[6]+A[8]+A[9] до n) считаем что числа в незаполненных позициях равны 1, но само число с 1 не начинаеться. Также проверяем вариант, что если число начинается с единиц. То количество вариантов умножается на это количество единиц, т.е. умножаем на n-i+1 (т.к. начальные единицы могут быть нулями по условию)

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

А почему только до 9 число К разбиваем на простые ведь максимальное значение к=9^N????

val_nnm · 07.11.2011, 17:20

Потомучто цифр только 9.
Например если k=9^n=3^(2*n)
тогда изначально мы рабтаем с массивом
A[2] = 0, A[3]=2*n, A[4]=0, A[5]=0, A[6]=0, A[7]=0, A[8]=0, A[9]=0
затем проверим
A[2] = 0, A[3]=2*n-2, A[4]=0, A[5]=0, A[6]=0, A[7]=0, A[8]=0, A[9]=1
A[2] = 0, A[3]=2*n-4, A[4]=0, A[5]=0, A[6]=0, A[7]=0, A[8]=0, A[9]=2
...
...
а закончим массивом
A[2] = 0, A[3]=0, A[4]=0, A[5]=0, A[6]=0, A[7]=0, A[8]=0, A[9]=n
(т.е. числом содержащим n девяток)

Ну в данном случае нам подойдёт только последный массив, остальные (n/2 штук) мы отбросим т.к. они недадут ни одного варианта. (внутренний цикл проверки от A[2]+A[3]+A[4]+A[5]+A[6]+A[6]+A[8]+A[9] до n. сума A для всех вариантов кроме последнего окажеться больше n)

p.s. k мы разбиваем полностью. так чтобы k=(2^A[2])*(3^A[3])*(5^A[5])*(7^A[7]) (если его полностью разбить на эти числа не получиться, то тогда ответ будет 0 вариантов т.к. небудет чисел удовлетворяющих заданному условию)
p.p.s. Сложнее всего будет придумать формула для подсчёта вариантов перестановок чисел. Я сам пока приблезительно представляю её вид, нужнобудет в интернете поискать из чего её можнобудет вывести.
p.p.p.s. В принцепе основную формула нашел. Надо начинать из комбинаторной формулы для перестановок с повторениями. И немного модифицировать её (это изза 0 в начале числа). Если соберётесь делать программу могу помочь вывести.

val_nnm · 07.11.2011, 23:22

Вот решил для истории написать программу.
Реализовал на C# может ктонибуть переведёт на C.
В своём верхнем посте забыл про цикл по восьмёркам. (в программе поправленно)
Для расчёта того, сколькими вариантами можно уложить числа.
Делаем цикл I = A[2]+A[3]+A[4]+A[5]+A[6]+A[6]+A[8]+A[9] .. n
Т.е. число начинаеться с n-I нулей. Чтобы заполнить оставшуюся часть добавляем еденици A[1] = I - A[2]+A[3]+A[4]+A[5]+A[6]+A[6]+A[8]+A[9] .
Дальше расчитываем количество вариантов «Перестановки с повтрениями» D= (A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[6]+A[8]+A[9])!/ A[1]!*A[2]!*A[3]!*A[4]!*A[5]!*A[6]!*A[6]!*A[8]!*A[9]! Но для ускорения в программе записал её в рекурентном виде.
A[1][i+1] = A[1][i]+1
D[i+1] = D[i]*(i+1)/A[1][i+1]
В результате получилась вот такая программа.
Она счтает и оптамальным методом и методом прямого перебора (для прямого перебора n>8 лучше не задовать, будет работать слишком долго)
Также для ускорения, сделал таблицу факториалов от 0 до 10 и занёс её в массив (чтобы каждый раз не пересчитывать)

Код:

using System;
namespace T2
{
	class MainClass
	{
		public static int SplitN (ref Int64 value, Int64 diveder)
		{
			int result = 0;
			while ((value % diveder)==0) {
				value = value / diveder;
				result++;
			}
			return result;
		}

		public static void Main (string[] args)
		{
			Console.WriteLine ("n=");
			Int32 n = Int32.Parse (Console.ReadLine ());
			if (n <= 0) {
				Console.WriteLine ("n должно быть больше 0");
				return;
			}
			if (n > 10) {
				Console.WriteLine ("n должно быть небольше 10");
				return;
			}

			Console.WriteLine ("k=");
			Int64 k = Int64.Parse (Console.ReadLine ());
			if (k <= 0) {
				Console.WriteLine ("k должно быть больше 0");
				return;
			}
			int[] A = new int[10];
			for (int i = 0; i<10; i++)
				A [i] = 0;
			Int64 temp = k;
			A [2] = SplitN (ref temp, 2);
			A [3] = SplitN (ref temp, 3);
			A [5] = SplitN (ref temp, 5);
			A [7] = SplitN (ref temp, 7);
			
			
			Int64[] Fact = new Int64[11];  // Таблица факториалов для ускорения работы
			Fact [0] = 1;
			for (int i = 1; i<11; i++) {
				Fact [i] = Fact [i - 1] * i;
			}
			Int64 s = 0;
			if (temp == 1) {
				for (int i4=0; i4<=A[2]/2; i4++) {
					A [2] -= i4 * 2;
					A [4] = i4;
					for (int i8=0; i8<=Math.Min(A[4],A[2]); i8++) {
						A [2] -= i8;
						A [4] -= i8;
						A [8] = i8;
						for (int i9=0; i9<=A[3]/2; i9++) {
							A [3] -= i9 * 2;
							A [9] = i9;
							for (int i6=0; i6<=Math.Min(A[2],A[3]); i6++) {
								A [6] = i6;
								A [2] -= i6;
								A [3] -= i6;
						
								int nd = A [2] + A [3] + A [4] + A [5] + A [6] + A [7] + A [8] + A [9];
								if (nd <= n) {
									Int64 d = Fact [nd];
									for (int i = 2; i<10; i++)
										d /= Fact [A [i]];
									A [1] = 0;
									for (int i = nd; i<=n; i++) {
										s += d;
										A [1]++;
										d = (d * (i + 1)) / A [1];
									}
								}
								A [3] += i6;
								A [2] += i6;
								A [6] = 0;
							}
							A [9] = 0;
							A [3] += i9 * 2;
						}
						A [8] = 0;
						A [4] += i8;
						A [2] += i8;
					}
					A [4] = 0;
					A [2] += i4 * 2;
				}
			}
			Console.WriteLine ("общее число вариантов S=" + s.ToString ());
			Int64 p = 1;
			for (int i = 1; i<=n; i++)
				p *= 10;
			s = 0;
			for (Int64 v = 0; v<p; v++) {
				Int64 t = v;
				Int64 w = 1;
				while (t > 0) {
					w *= t % 10;
					t = t / 10;
				}
				if (w == k) {
					s++; 
				}
			}
			Console.WriteLine ("общее число вариантов S=" + s.ToString ());
			Console.ReadLine ();
		}
	}
}

p.s. Перечетав задание Немого начал сомниваться. (я понял так что если задать n=2 k=4 то будут учтены числа 04 22 41 14)?
а если исключить числа начинающиеся с 0. (т. е. n=2 k=4 даст числа 22 41 14) тогда

Код:

...
...
								int nd = A [2] + A [3] + A [4] + A [5] + A [6] + A [7] + A [8] + A [9];
								if (nd <= n) {
									A[1] = n-nd;
									Int64 d = Fact [n];
									for (int i = 1; i<10; i++)
										d /= Fact [A [i]];
									s += d;
								}
								A [3] += i6;
								A [2] += i6;
								A [6] = 0;...
...
			for (Int64 v = 0; v<p; v++) {
				Int64 t = v;
				Int64 w = 1;
				for (int i = 0;i<n;i++)
				{
					w *= t % 10;
					t = t / 10;
				}
				if (w == k) {
					s++; 
				}
			}
...
...

06.11.2011, 01:51	#1
sheff123 Пользователь Регистрация: 06.11.2011 Сообщений: 21	задачf на комбинаторику Определить количество чисел состоящих из n десятичных разрядов (n – натуральное число, вводится пользователем, n <= 10) произведение цифр которого равно числу K (натуральное число, вводится пользователем, K < 9n). Учитывать, что число может начинаться с нулей: 0042345 код на C)

06.11.2011, 09:36	#2
NetSpace Участник клуба Регистрация: 03.06.2009 Сообщений: 1,871	т.е. например, число 345, 354, 435, 453 ,543, 534 - при перемножнении их разрядов 543 = 60 - они все дадут одно и то же самое число. далее, получаестя, вам необходимо узнать сколько вообще в числе разрядов, например, в числе 1000 их 4, а в нашем случае, скажем, 345 - их всего 3 (т.к. всего 3 цифры в числе). тогда таких чисел будет всего 3! = 6 (смотрите верхний ряд чисел и считайте). Ответ: всего 6 чисел, состоящих из 3 разрядов дадут такой вот результат. Факториал надо использовать, если я правильно понял задачу... Программирование - это единственный способ заставить компьютер делать то, что тебе хочется, а не то, что приходится.

07.11.2011, 13:50	#6
val_nnm Форумчанин Регистрация: 18.10.2009 Сообщений: 185	В принципе задачу можно решить и оптимальным образом (перебирая несколько тысяч вариантов вместо миллиардов). Для начала, число K нужно разложить на простые числа в диапазоне от 2 до 9 (т.е. 2, 3, 5, 7) Скажем, количество каждых сомножителей запишем в массив A[]. Т.е. A[2] – количество вхождений числа 2 в разложение числа K. Такое разложение будет единственным. Дальше нужно проверить несколько вариантов две двойки могут дать цифру 4 две тройки могут дать цифру 9 тройка и двойка могут дать цифру 6 (остальные варианты не проверяем т.к. они дают числа большие 9) Т.е. сделать примерно такой цикл Код: `For (int i4=0;i4++;i4<=A[2]/2) { A[2] -= i42; A[4] += 1; For (int i9=0;i9++;i9<A[3]/2) { A[3]-=i92; A[9]+=1; For (int i6=0;i6++;i6<min(A[2],A[3])) { A[6]+=1; A[2]-=i6; A[3] -= i6; // Здесь в массиве A мы получаем варианты цифр из которых будет состоять искомые числа A[3] +=i6; A[2] +=i6; A[6] -=1; } A[9]-=1; A[3]+=i92; } A[4]-=1; A[2] += i42; }` Дальше для каждого варианта разложения Рассчитываем, сколькими вариантами эти цифры можно уложить для 1 значного числа для 2х значного числа и.т.д. до n (вернее i = A[2]+A[3]+A[4]+A[5]+A[6]+A[6]+A[8]+A[9] до n) считаем что числа в незаполненных позициях равны 1, но само число с 1 не начинаеться. Также проверяем вариант, что если число начинается с единиц. То количество вариантов умножается на это количество единиц, т.е. умножаем на n-i+1 (т.к. начальные единицы могут быть нулями по условию) Это конечно очень грубый план, и скорее направление в котором можно размышлять. Но на реализацию всёго этого (у профессионального программиста) уйдёт полдня как минимум (а может и больше). На С# пишу лучше чем на русском. "У меня правильнописание хромает. Оно хорошее, но почему-то хромает." Последний раз редактировалось val_nnm; 07.11.2011 в 14:07.

07.11.2011, 17:20	#8
val_nnm Форумчанин Регистрация: 18.10.2009 Сообщений: 185	Потомучто цифр только 9. Например если k=9^n=3^(2n) тогда изначально мы рабтаем с массивом A[2] = 0, A[3]=2n, A[4]=0, A[5]=0, A[6]=0, A[7]=0, A[8]=0, A[9]=0 затем проверим A[2] = 0, A[3]=2n-2, A[4]=0, A[5]=0, A[6]=0, A[7]=0, A[8]=0, A[9]=1 A[2] = 0, A[3]=2n-4, A[4]=0, A[5]=0, A[6]=0, A[7]=0, A[8]=0, A[9]=2 ... ... а закончим массивом A[2] = 0, A[3]=0, A[4]=0, A[5]=0, A[6]=0, A[7]=0, A[8]=0, A[9]=n (т.е. числом содержащим n девяток) Ну в данном случае нам подойдёт только последный массив, остальные (n/2 штук) мы отбросим т.к. они недадут ни одного варианта. (внутренний цикл проверки от A[2]+A[3]+A[4]+A[5]+A[6]+A[6]+A[8]+A[9] до n. сума A для всех вариантов кроме последнего окажеться больше n) p.s. k мы разбиваем полностью. так чтобы k=(2^A[2])(3^A[3])(5^A[5])(7^A[7]) (если его полностью разбить на эти числа не получиться, то тогда ответ будет 0 вариантов т.к. небудет чисел удовлетворяющих заданному условию) p.p.s. Сложнее всего будет придумать формула для подсчёта вариантов перестановок чисел. Я сам пока приблезительно представляю её вид, нужнобудет в интернете поискать из чего её можнобудет вывести. p.p.p.s. В принцепе основную формула нашел. Надо начинать из комбинаторной формулы для перестановок с повторениями. И немного модифицировать её (это изза 0 в начале числа). Если соберётесь делать программу могу помочь вывести. На С# пишу лучше чем на русском. "У меня правильнописание хромает. Оно хорошее, но почему-то хромает." Последний раз редактировалось val_nnm; 07.11.2011 в 18:04.*

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
C. Задача на комбинаторику	_zaq357	Помощь студентам	0	25.10.2011 22:17
Задача на комбинаторику	Rad-X	Помощь студентам	1	13.02.2011 17:18
помогите с задачей на комбинаторику	Alex26RusLink	Помощь студентам	5	27.10.2009 21:22